kombinacje między dwiema listami?

187

Minęło trochę czasu i mam problem z owinięciem głowy algorytmem, który staram się stworzyć. Zasadniczo mam dwie listy i chcę uzyskać wszystkie kombinacje dwóch list.

Być może nie tłumaczę tego poprawnie, oto przykład.

name = 'a', 'b'
number = 1, 2

wyjście w tym przypadku byłoby:

1.  A1 B2
2.  B1 A2

Problem polega na tym, że mogę mieć więcej pozycji w zmiennej „name” niż pozycji w zmiennej „number” (liczba zawsze będzie równa lub mniejsza niż zmienna name).

Jestem zdezorientowany, jak wykonać wszystkie kombinacje (zagnieżdżone dla pętli?), A jeszcze bardziej zdezorientowany w logice, aby przesunąć elementy w zmiennej name w przypadku, gdy w nazwie jest więcej elementów niż na liście liczb.

Nie jestem najlepszym programistą, ale myślę, że mogę spróbować, jeśli ktoś pomoże mi wyjaśnić logikę / algorytm, aby to osiągnąć. Właśnie utknąłem na zagnieżdżonych pętlach.

Aktualizacja:

Oto wynik z 3 zmiennymi i 2 liczbami:

name = 'a', 'b', 'c'
number = 1, 2

wynik:

1.  A1 B2
2.  B1 A2
3.  A1 C2
4.  C1 A2
5.  B1 C2
6.  C1 B2
użytkownik1735075
źródło
1
@ dm03514 Widziałem to i znalazłem przykłady dla nieco podobnych celów przy użyciu itertools, ale prototypuję w pythonie, ale napiszę końcowy kod w innym języku, więc nie chcę używać narzędzi, które nie są dostępne w inny sposób.
user1735075
1
To, o co prosisz, naprawdę nie ma sensu. Jeśli pierwsza lista zawiera A, B, C, a druga zawiera 1,2, czego byś się spodziewał? Można to zrobić, jeśli podany przykład zawiera 4 różne wyniki po jednej literze i po jednej cyfrze (A1, A2, B1, B2) lub jeśli obie listy muszą mieć ten sam rozmiar.
interjay
1
Zgadzam się z interjay. Podaj wynik w przypadku różnej wielkości, w przeciwnym razie nie będzie możliwe podanie ogólnego rozwiązania.
Bakuriu
Cześć Wszyscy, zaktualizowałem odpowiedź, aby wyświetlić wynik z 3 nazwiskami i 2 liczbami. Myślałem, że dobrze to wytłumaczyłem, nie wiem, dlaczego głosowanie negatywne.
user1735075

Odpowiedzi:

93

Uwaga : Ta odpowiedź dotyczy konkretnego pytania zadanego powyżej. Jeśli jesteś tutaj od Google i po prostu szukasz sposobu na uzyskanie kartezjańskiego produktu w Pythonie, itertools.productlub proste zrozumienie listy może być tym, czego szukasz - zobacz inne odpowiedzi.


Załóżmy len(list1) >= len(list2). Wtedy to, co wydaje się chce to wziąć wszystkie permutacje długości len(list2)od list1i dopasować je z pozycji z listy2. W python:

import itertools
list1=['a','b','c']
list2=[1,2]

[list(zip(x,list2)) for x in itertools.permutations(list1,len(list2))]

Zwroty

[[('a', 1), ('b', 2)], [('a', 1), ('c', 2)], [('b', 1), ('a', 2)], [('b', 1), ('c', 2)], [('c', 1), ('a', 2)], [('c', 1), ('b', 2)]]
interjay
źródło
1
Rezultat jest dokładnie tym, czego chcę, ale czy można podzielić logikę, jak to zrobić? Jeśli przekonwertuję mój kod na C lub Java, nie będę miał dostępu do zip lub itertools (chociaż ułatwiają życie)
user1735075
3
@ user1735075 Zajrzyj do dokumentacji
lenistwo
1
@ user1735075: czy wiesz, że Python jest oprogramowaniem typu open source? Możesz więc po prostu pobrać źródła i zobaczyć, co oni robią. +1 panowi Steakowi za wskazanie, że dokumentacja faktycznie zawiera przykładową implementację, która nie używa zipi nie jest podobna.
Bakuriu
2
dosłownie nie mogę tego uruchomić, nawet na twoim przykładzie ... wszystko, co dostaję, to lista obiektów zip ..: |
m1nkeh,
1
@logic zapewnia akceptowane rozwiązanie.
Bernhard Wagner
500

Najprostszym sposobem jest użycie itertools.product:

a = ["foo", "melon"]
b = [True, False]
c = list(itertools.product(a, b))
>> [("foo", True), ("foo", False), ("melon", True), ("melon", False)]
DrIDK
źródło
11
OP nie prosiło o kartezjański produkt, a ta odpowiedź (podobnie jak większość innych) nie daje oczekiwanego rezultatu określonego w pytaniu.
interjay 18.07.17
17
@ interjay masz rację, ale ponieważ zbyt wielu ludzi uważa tę odpowiedź za poprawną, mogę jedynie założyć, że tytuł pytania nie ma kontekstu.
xpy,
3
@xpy Tytuł jest za krótki, aby wszystko wyjaśnić. Dlatego musisz przeczytać aktualne pytanie.
interjay
10
OP chciał permuacji, ale Google wysyła do tej odpowiedzi każdego, kto szuka kombinacji (jak ja) - cieszę się, że ma 8 razy więcej głosów!
Josh Friedlander
160

Może być prostszy niż najprostszy powyżej:

>>> a = ["foo", "bar"]
>>> b = [1, 2, 3]
>>> [(x,y) for x in a for y in b]  # for a list
[('foo', 1), ('foo', 2), ('foo', 3), ('bar', 1), ('bar', 2), ('bar', 3)]
>>> ((x,y) for x in a for y in b)  # for a generator if you worry about memory or time complexity.
<generator object <genexpr> at 0x1048de850>

bez importu

logika
źródło
Najlepsze rozwiązanie! Dziękuję Ci! Inne rozwiązania są po prostu błędne lub działają tylko w określonych przypadkach, np. A> b itp.
Philipp Schwarz
3
Najbardziej Pythoniczne rozwiązanie! (i pozwala uniknąć niepotrzebnego importu)
Dalker
6
Złożoność czasu wynosi O (n ^ 2)
Deepak Sharma
2
Zakłady rozwiązanie !! Gołe podstawy to zawsze najlepsza droga
Sabyasachi,
22

Szukałem listy pomnożonej przez siebie tylko z unikatowymi kombinacjami, która jest zapewniona jako ta funkcja.

import itertools
itertools.combinations(list, n_times)

Tutaj jako fragment dokumentacji Pythona na temat itertools To może pomóc ci znaleźć to, czego szukasz.

Combinatoric generators:

Iterator                                 | Results
-----------------------------------------+----------------------------------------
product(p, q, ... [repeat=1])            | cartesian product, equivalent to a 
                                         |   nested for-loop
-----------------------------------------+----------------------------------------
permutations(p[, r])                     | r-length tuples, all possible 
                                         |   orderings, no repeated elements
-----------------------------------------+----------------------------------------
combinations(p, r)                       | r-length tuples, in sorted order, no 
                                         |   repeated elements
-----------------------------------------+----------------------------------------
combinations_with_replacement(p, r)      | r-length tuples, in sorted order, 
                                         | with repeated elements
-----------------------------------------+----------------------------------------
product('ABCD', repeat=2)                | AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)                  | AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)                  | AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2) | AA AB AC AD BB BC BD CC CD DD
ThorSummoner
źródło
11

Możesz spróbować zapoznać się z listą zawierającą jeden wiersz:

>>> [name+number for name in 'ab' for number in '12']
['a1', 'a2', 'b1', 'b2']
>>> [name+number for name in 'abc' for number in '12']
['a1', 'a2', 'b1', 'b2', 'c1', 'c2']
Idanmel
źródło
11

najlepszym sposobem na znalezienie wszystkich kombinacji dla dużej liczby list jest:

import itertools
from pprint import pprint

inputdata = [
    ['a', 'b', 'c'],
    ['d'],
    ['e', 'f'],
]
result = list(itertools.product(*inputdata))
pprint(result)

wynikiem będzie:

[('a', 'd', 'e'),
 ('a', 'd', 'f'),
 ('b', 'd', 'e'),
 ('b', 'd', 'f'),
 ('c', 'd', 'e'),
 ('c', 'd', 'f')]
Ishan Rastogi
źródło
Dzięki, świetna odpowiedź!
toinbis
10

Lub odpowiedź KISS dla krótkich list:

[(i, j) for i in list1 for j in list2]

Nie tak wydajne jak itertools, ale używasz Pythona, więc wydajność już nie jest twoim głównym problemem ...

Lubię też wszystkie inne odpowiedzi!

Fletch F Fletch
źródło
8

niewielkie ulepszenie odpowiedzi z interjay, aby wynik był spłaszczony.

>>> list3 = [zip(x,list2) for x in itertools.permutations(list1,len(list2))]
>>> import itertools
>>> chain = itertools.chain(*list3)
>>> list4 = list(chain)
[('a', 1), ('b', 2), ('a', 1), ('c', 2), ('b', 1), ('a', 2), ('b', 1), ('c', 2), ('c', 1), ('a', 2), ('c', 1), ('b', 2)]

referencja z tego linku

Mass Zhou
źródło
4

Bez narzędzi

[(list1[i], list2[j]) for i in xrange(len(list1)) for j in xrange(len(list2))]
użytkownik3684792
źródło
4

Odpowiadając na pytanie „biorąc pod uwagę dwie listy, znajdź wszystkie możliwe kombinacje par jednego elementu z każdej listy” i używając podstawowej funkcjonalności Pythona (tj. Bez itertools), a tym samym ułatwiając replikację dla innych języków programowania:

def rec(a, b, ll, size):
    ret = []
    for i,e in enumerate(a):
        for j,f in enumerate(b):
            l = [e+f]
            new_l = rec(a[i+1:], b[:j]+b[j+1:], ll, size)
            if not new_l:
                ret.append(l)
            for k in new_l:
                l_k = l + k
                ret.append(l_k)
                if len(l_k) == size:
                    ll.append(l_k)
    return ret

a = ['a','b','c']
b = ['1','2']
ll = []
rec(a,b,ll, min(len(a),len(b)))
print(ll)

Zwroty

[['a1', 'b2'], ['a1', 'c2'], ['a2', 'b1'], ['a2', 'c1'], ['b1', 'c2'], ['b2', 'c1']]
informatyk
źródło
2

Lepsze odpowiedzi na to działają tylko w przypadku określonych długości dostarczonych list.

Oto wersja, która działa na dowolne długości danych wejściowych. Wyjaśnia również algorytm pod względem matematycznych koncepcji kombinacji i permutacji.

from itertools import combinations, permutations
list1 = ['1', '2']
list2 = ['A', 'B', 'C']

num_elements = min(len(list1), len(list2))
list1_combs = list(combinations(list1, num_elements))
list2_perms = list(permutations(list2, num_elements))
result = [
  tuple(zip(perm, comb))
  for comb in list1_combs
  for perm in list2_perms
]

for idx, ((l11, l12), (l21, l22)) in enumerate(result):
  print(f'{idx}: {l11}{l12} {l21}{l22}')

To daje:

0: A1 B2
1: A1 C2
2: B1 A2
3: B1 C2
4: C1 A2
5: C1 B2
Steve Alexander
źródło