Jak wygenerować wszystkie permutacje listy w Pythonie, niezależnie od rodzaju elementów na tej liście?
Na przykład:
permutations([])
[]
permutations([1])
[1]
permutations([1, 2])
[1, 2]
[2, 1]
permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
python
algorithm
permutation
combinatorics
python-2.5
Ricardo Reyes
źródło
źródło
Odpowiedzi:
Począwszy od Pythonie 2.6 (i jeśli jesteś w Pythonie 3) masz standardową Biblioteka narzędziem do tego:
itertools.permutations
.Jeśli z jakiegoś powodu używasz starszego języka Python (<2.6) lub po prostu chcesz wiedzieć, jak to działa, oto jedno fajne podejście, zaczerpnięte z http://code.activestate.com/recipes/252178/ :
Kilka alternatywnych podejść wymieniono w dokumentacji
itertools.permutations
. Tutaj jest jeden:I inny, oparty na
itertools.product
:źródło
for i in range(len(elements))
zamiastfor i in range(len(elements)+1)
. W rzeczywistości wyodrębniony elementelements[0:1]
może znajdować się wlen(elements)
różnych pozycjach, w rezultacie nielen(elements)+1
.Od wersji Python 2.6 :
(zwrócony jako generator. Użyj,
list(permutations(l))
aby powrócić jako lista.)źródło
r
parametr, np.itertools.permutations([1,2,3], r=2)
Który wygeneruje wszystkie możliwe permutacje, wybierając 2 elementy:[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
Poniższy kod TYLKO w języku Python 2.6 i nowszych
Najpierw zaimportuj
itertools
:Permutacja (kolejność ma znaczenie):
Kombinacja (kolejność NIE ma znaczenia):
Produkt kartezjański (z kilkoma iteracjami):
Produkt kartezjański (z jednym iterowalnym i samym):
źródło
nazywany jako:
źródło
Wynik:
Gdy zmieniam zawartość listy, jako dane wejściowe wymagany jest zmienny typ sekwencji. Np. Zadziała
perm(list("ball"))
iperm("ball")
nie zadziała, ponieważ nie można zmienić łańcucha.Ta implementacja Pythona jest zainspirowana algorytmem przedstawionym w książce Computer Algorytmy Horowitza, Sahniego i Rajasekerana .
źródło
To rozwiązanie implementuje generator, aby uniknąć przechowywania wszystkich permutacji w pamięci:
źródło
W funkcjonalnym stylu
Wynik:
źródło
Poniższy kod jest permutacją w miejscu danej listy, zaimplementowaną jako generator. Ponieważ zwraca tylko referencje do listy, listy nie należy modyfikować poza generatorem. Rozwiązanie nie jest rekurencyjne, więc zużywa mało pamięci. Działa również z wieloma kopiami elementów na liście danych wejściowych.
źródło
Moim zdaniem dość oczywistym sposobem może być:
źródło
Wynik:
źródło
Użyłem algorytmu opartego na systemie liczb silni - dla listy długości n można złożyć każdą pozycję permutacji według pozycji, wybierając spośród pozycji pozostawionych na każdym etapie. Masz n wyborów dla pierwszego elementu, n-1 dla drugiego i tylko jeden dla ostatniego, więc możesz użyć cyfr liczby w systemie liczb silni jako wskaźników. W ten sposób liczby od 0 do n! -1 odpowiadają wszystkim możliwym kombinacjom w porządku leksykograficznym.
wynik:
Ta metoda nie jest rekurencyjna, ale na moim komputerze jest nieco wolniejsza i xrange podnosi błąd, gdy n! jest zbyt duży, aby go przekonwertować na długą liczbę całkowitą C (dla mnie n = 13). Wystarczyło, gdy go potrzebowałem, ale to nie są narzędzia iteracyjne.
źródło
Zauważ, że ten algorytm ma
n factorial
złożoność czasową, gdzien
jest długością listy danych wejściowychWydrukuj wyniki w biegu:
Przykład:
Wynik:
źródło
Rzeczywiście można iterować po pierwszym elemencie każdej permutacji, jak w odpowiedzi tzw. Bardziej efektywne jest jednak napisanie tego rozwiązania w ten sposób:
To rozwiązanie jest o 30% szybsza, widocznie dzięki rekursji, kończący się
len(elements) <= 1
zamiast0
. Jest również znacznie bardziej wydajna pod względem pamięci, ponieważ wykorzystuje funkcję generatora (poprzezyield
), jak w rozwiązaniu Riccardo Reyesa.źródło
Jest to zainspirowane wdrożeniem Haskell przy użyciu listy:
źródło
Regularna implementacja (brak wydajności - zrobi wszystko w pamięci):
Realizacja plonu:
Podstawową ideą jest przejście przez wszystkie elementy w tablicy dla 1. pozycji, a następnie w 2. pozycji przejrzenie wszystkich pozostałych elementów bez wybranego elementu dla 1. itd. Można to zrobić z rekurencją , gdzie kryterium zatrzymania jest dotarcie do tablicy 1 elementu - w takim przypadku zwracamy tę tablicę.
źródło
perms = getPermutations(array[:i] + array[i+1:])
numpy
tablicę _>getPermutations(np.array([1, 2, 3]))
, widzę, że działa dla listy, właśnie się pomyliłem, bo jest func argarray
:)numba
i zachłanniełem szybkością, więc próbowałem używać go wyłącznie znumpy
tablicamiNa wydajność, numpy rozwiązanie inspirowane Knuth (P22):
Kopiowanie dużych bloków pamięci oszczędza czas - jest 20 razy szybszy niż
list(itertools.permutations(range(n))
:źródło
źródło
Oto algorytm, który działa na liście bez tworzenia nowych list pośrednich podobnych do rozwiązania Ber'a na https://stackoverflow.com/a/108651/184528 .
Możesz sam wypróbować kod tutaj: http://repl.it/J9v
źródło
Piękno rekurencji:
źródło
Ten algorytm jest najskuteczniejszy, pozwala uniknąć przekazywania tablic i manipulacji w wywołaniach rekurencyjnych, działa w Pythonie 2, 3:
Stosowanie:
źródło
źródło
INNE PODEJŚCIE (bez bibliotek)
Dane wejściowe mogą być ciągiem lub listą
źródło
[1, 2, 3]
zwroty[6, 6, 6, 6, 6, 6]
print(permutation(['1','2','3']))
Uwaga: wtyczka bezkształtna według autora pakietu. :)
Trotter pakiet różni się od większości implementacji tym, że generuje listę pseudo, które w rzeczywistości nie zawierają permutacje ale raczej opisują mapowania między permutacji i odpowiednich pozycjach w kolejności, co umożliwia pracę z bardzo dużymi „list” permutacji, jak pokazano w tym demo które wykonuje natychmiastowe operacje i wyszukiwania na pseudo-liście „zawierającej” wszystkie permutacje liter w alfabecie, bez użycia większej ilości pamięci lub przetwarzania niż typowa strona internetowa.
W każdym razie, aby wygenerować listę permutacji, możemy wykonać następujące czynności.
Wynik:
źródło
Wygeneruj wszystkie możliwe permutacje
Używam python3.4:
Przypadki testowe:
źródło
Aby zaoszczędzić wam wielu godzin poszukiwań i eksperymentów, oto nierekurencyjne rozwiązanie permutaions w Pythonie, które działa również z Numba (od wersji 0.41):
Aby zrobić wrażenie na temat wydajności:
Więc używaj tej wersji tylko wtedy, gdy musisz wywołać ją z njitted funkcji, w przeciwnym razie wolisz implementację itertools.
źródło
Widzę wiele iteracji wewnątrz tych funkcji rekurencyjnych, nie do końca czystą rekurencję ...
więc dla tych z was, którzy nie mogą wytrzymać choćby jednej pętli, oto rażące, całkowicie niepotrzebne, w pełni rekurencyjne rozwiązanie
źródło
Inne rozwiązanie:
źródło
Moje rozwiązanie Python:
źródło
Wyjście: [„abc”, „acb”, „bac”, „bca”, „cab”, „cba”]
źródło
Za pomocą
Counter
źródło