Mam listę z 15 liczbami i muszę napisać kod, który wygeneruje wszystkie 32 768 kombinacji tych liczb.
Znalazłem trochę kodu (autorstwa Googlinga), który najwyraźniej robi to, czego szukam, ale znalazłem kod dość nieprzejrzysty i nieufnie go używam. Plus mam wrażenie, że musi być bardziej eleganckie rozwiązanie.
Jedyne, co przychodzi mi do głowy, to po prostu przechodzenie przez liczby całkowite dziesiętne 1–32768 i konwertowanie ich na binarne, a następnie użycie reprezentacji binarnej jako filtra do wybrania odpowiednich liczb.
Czy ktoś zna lepszy sposób? Korzystanie map()
, może być?
python
combinations
Ben
źródło
źródło
product
itp.)Odpowiedzi:
Spójrz na itertools.combinations :
Od wersji 2.6 baterie są dołączone!
źródło
list(itertools.combinations(iterable, r))
r
, tj. kombinacje podsekwencji o dowolnej długości elementów.Ta odpowiedź pominęła jeden aspekt: OP poprosił o WSZYSTKIE kombinacje ... nie tylko kombinacje długości „r”.
Więc musiałbyś albo przejść przez wszystkie długości „L”:
Lub - jeśli chcesz wpaść w zakłopotanie (lub zgiąć mózg tego, kto czyta twój kod po tobie) - możesz wygenerować łańcuch generatorów „kombinacji ()” i iterować przez to:
źródło
powerset()
funkcja generatora w sekcji przepisów witertools
dokumentacji jest prostsza, potencjalnie zużywa mniej pamięci i prawdopodobnie jest szybsza niż pokazana tutaj implementacja.itertools.combinations
zachowuje porządek pozycji na listach, które daje. Zatem jeśli dane wejściowe są posortowane leksykalnie, wówczas każde z nich również będzie.itertools.combinations
generuje kombinacje k wśród nw porządku leksykograficznym, ale nie wszystkie kombinacje do k wśród n.powerset
generuje wszystkie kombinacje do k, ale nie w porządku leksykograficznym, o ile rozumiem: powerset ([1,2]) -> [(), (1,), (2,), (1, 2)] . Czy nie powinno to być: [(), (1,), (1, 2), (2,)]?Oto leniwy jednowarstwowy, również przy użyciu itertools:
Główna idea leżąca u podstaw tej odpowiedzi: istnieją 2 ^ N kombinacje - takie same jak liczba ciągów binarnych o długości N. Dla każdego ciągu binarnego wybierasz wszystkie elementy odpowiadające „1”.
Rzeczy do rozważenia:
len(...)
naitems
(obejście: jeśliitems
jest coś w rodzaju iterable jak generator, przekształcić go w liście najpierwitems=list(_itemsArg)
)items
nie była losowa (obejście: nie bądź szalony){2,2,1}
i{2,1,1}
zarówno upadek woli{2,1}
(Obejście: zastosowaniacollections.Counter
jako zamiennik dlaset
, jest to w zasadzie multiset ... choć może trzeba późniejszego wykorzystaniatuple(sorted(Counter(...).elements()))
, jeśli jest to potrzebne, aby być hashable)Próbny
źródło
W komentarzach pod bardzo pozytywną odpowiedzią @Dan H wspomina się o
powerset()
przepisie witertools
dokumentacji - w tym jednym autorstwa Dana . Jednak do tej pory nikt nie opublikował go jako odpowiedzi. Ponieważ jest to prawdopodobnie jedno z lepszych, jeśli nie najlepsze podejście do problemu - i przy odrobinie zachęty ze strony innego komentatora, pokazano to poniżej. Ta funkcja tworzy wszystkie unikalne kombinacje elementów listy o każdej możliwej długości (w tym te zawierające zero i wszystkie elementy).Uwaga : W przypadku, subtelnie różne, celem jest uzyskanie tylko kombinacje unikalnych elementów, zmienić linię
s = list(iterable)
dos = list(set(iterable))
wyeliminowania wszelkich zduplikowane elementy. Niezależnie od tego, żeiterable
ostatecznie zostanie przekształcony wlist
środek, będzie on działał z generatorami (w przeciwieństwie do kilku innych odpowiedzi).Wynik:
źródło
list()
konwersja?Oto jeden z rekurencją:
źródło
new_data = copy.copy(data)
- ten wiersz jest niepotrzebny, o ile widzę, nie ma na nic wpływuTen jednowierszowy udostępnia wszystkie kombinacje (między
0
in
elementy, jeśli oryginalna lista / zestaw zawieran
odrębne elementy) i używa metody rodzimejitertools.combinations
:Python 2
Python 3
Dane wyjściowe będą:
Wypróbuj online:
http://ideone.com/COghfX
źródło
['b', 'a']
.TypeError: can only concatenate list (not "map") to list
Zgadzam się z Danem H, że Ben rzeczywiście poprosił o wszystkie kombinacje.
itertools.combinations()
nie podaje wszystkich kombinacji.Innym problemem jest to, że jeśli iterowalność danych wejściowych jest duża, być może lepiej jest zwrócić generator zamiast wszystkiego na liście:
źródło
Jest to podejście, które można łatwo przenieść na wszystkie języki programowania obsługujące rekurencję (bez narzędzi itert, bez wydajności, bez zrozumienia listy) :
źródło
Za pomocą tego prostego kodu możesz wygenerować wszystkie kombinacje listy w pythonie
Wynik byłby:
źródło
Pomyślałem, że dodam tę funkcję dla tych, którzy szukają odpowiedzi bez importowania itertools lub innych dodatkowych bibliotek.
Proste użycie generatora plonu:
Dane wyjściowe z powyższego przykładu użycia:
źródło
Oto jeszcze jedno rozwiązanie (jednowierszowe), polegające na użyciu
itertools.combinations
funkcji, ale tutaj używamy rozumienia podwójnej listy (w przeciwieństwie do pętli for lub sumy):Próbny:
źródło
wynik
źródło
Poniżej znajduje się „standardowa odpowiedź rekurencyjna”, podobna do innej podobnej odpowiedzi https://stackoverflow.com/a/23743696/711085 . (Nie musimy realistycznie martwić się brakiem miejsca na stosie, ponieważ nie ma możliwości przetworzenia wszystkich permutacji N!).
Odwiedza kolejno każdy element i albo go bierze, albo opuszcza (możemy bezpośrednio zobaczyć liczność 2 ^ N z tego algorytmu).
Próbny:
źródło
Korzystanie ze zrozumienia listy:
Dane wyjściowe byłyby:
źródło
Ten kod wykorzystuje prosty algorytm z zagnieżdżonymi listami ...
źródło
""
).Wiem, że to o wiele bardziej praktyczny w użyciu itertools aby uzyskać wszystkie kombinacje, ale można to osiągnąć częściowo tylko listowego jeśli tak się stało pragnienie, przyznane chcesz kodu a lot
Dla kombinacji dwóch par:
W przypadku kombinacji trzech par jest to tak proste:
Wynik jest identyczny z użyciem kombinacji itertools.com:
źródło
Bez korzystania z itertools:
źródło
Oto dwie implementacje
itertools.combinations
Jeden, który zwraca listę
Zwraca się generator
Należy pamiętać, że zaleca się udostępnienie tych funkcji pomocniczych, ponieważ argument poprzedzający jest statyczny i nie zmienia się przy każdym wywołaniu
To bardzo powierzchowny przypadek, ale lepiej być bezpiecznym niż żałować
źródło
Co powiesz na to… użyłem ciągu zamiast listy, ale to samo… ciąg można traktować jak listę w Pythonie:
źródło
Połączenie z itertools
Dzięki
źródło
Bez
itertools
w Pythonie 3 możesz zrobić coś takiego:gdzie początkowo
carry = "".
źródło
3 funkcje:
źródło
To jest moja realizacja
źródło
Możesz także użyć funkcji powerset z doskonałego
more_itertools
pakietu.Możemy również zweryfikować, czy spełnia on wymagania OP
źródło
źródło
Jeśli ktoś szuka odwróconej listy, tak jak ja:
źródło
źródło