Powiedzmy, że mam listę n elementów, wiem, że jest n! możliwe sposoby zamówienia tych elementów. Jaki jest algorytm generujący wszystkie możliwe uporządkowania tej listy? Przykład, mam listę [a, b, c]. Algorytm zwróciłby [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b , a]].
Czytam to tutaj http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
Ale Wikipedia nigdy nie była dobra w wyjaśnianiu. Niewiele z tego rozumiem.
algorithm
list
permutation
fent
źródło
źródło
Odpowiedzi:
Zasadniczo dla każdego elementu od lewej do prawej generowane są wszystkie permutacje pozostałych elementów (i każdy z nich jest dodawany z bieżącymi elementami). Można to zrobić rekurencyjnie (lub iteracyjnie, jeśli lubisz ból), aż do osiągnięcia ostatniego elementu, w którym to momencie jest tylko jedno możliwe zamówienie.
Tak więc z listą [1, 2, 3, 4] generowane są wszystkie permutacje, które zaczynają się od 1, a następnie wszystkie permutacje zaczynające się od 2, potem 3 i 4.
To skutecznie redukuje problem ze znalezienia permutacji listy czterech pozycji do listy trzech pozycji. Po zredukowaniu list pozycji do 2, a następnie 1, wszystkie zostaną znalezione.
Przykład pokazujący permutacje procesów przy użyciu 3 kolorowych kul:
(z https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB. svg )
źródło
Oto algorytm w Pythonie, który działa w miejscu na tablicy:
Możesz sam wypróbować kod tutaj: http://repl.it/J9v
źródło
Jest już tutaj wiele dobrych rozwiązań, ale chciałbym podzielić się tym, jak samodzielnie rozwiązałem ten problem i mam nadzieję, że może to być pomocne dla kogoś, kto również chciałby znaleźć własne rozwiązanie.
Po zastanowieniu się nad problemem doszedłem do dwóch następujących wniosków:
L
rozmiarówn
będzie równa liczba rozwiązań zaczynających się od L 1 , L 2 ... L n elementów listy. Ponieważ w sumie istniejąn!
permutacje listy rozmiarówn
, otrzymujemyn! / n = (n-1)!
permutacje w każdej grupie.[a,b]
i[b,a]
.Korzystając z tych dwóch prostych pomysłów, wyprowadziłem następujący algorytm:
Oto jak zaimplementowałem to w C #:
źródło
Odpowiedź Wikipedii na „porządek leksykograficzny” wydaje mi się całkowicie jednoznaczna w stylu książki kucharskiej. Przytacza XIV-wieczne pochodzenie algorytmu!
Właśnie napisałem szybką implementację algorytmu Wikipedii w Javie jako czek i nie było problemu. Ale to, co masz w swoim Q jako przykład, to NIE "lista wszystkich permutacji", ale "LISTA wszystkich permutacji", więc Wikipedia nie będzie dla ciebie zbyt pomocna. Potrzebujesz języka, w którym listy permutacji są wykonalne. I wierz mi, listy długie na kilka miliardów zwykle nie są obsługiwane w językach imperatywnych. Naprawdę chcesz, aby nie ścisły funkcjonalny język programowania, w którym listy są obiektem pierwszej klasy, aby wydobyć rzeczy, nie doprowadzając maszyny do bliskiej śmierci Wszechświata.
To łatwe. W standardowym języku Haskell lub dowolnym nowoczesnym języku FP:
i
źródło
Jak powiedział WhirlWind, zaczynasz od początku.
Zamieniasz kursor z każdą pozostałą wartością, w tym z samym kursorem, są to wszystkie nowe instancje (użyłem
int[]
iarray.clone()
w przykładzie).Następnie wykonaj permutacje na wszystkich tych różnych listach, upewniając się, że kursor znajduje się o jeden po prawej stronie.
Gdy nie ma już pozostałych wartości (kursor znajduje się na końcu), wydrukuj listę. To jest warunek zatrzymania.
źródło
Utrzymanie rekurencji zawsze wymaga wysiłku umysłowego. A w przypadku dużych liczb silnia jest z łatwością ogromna, a przepełnienie stosu z łatwością będzie problemem.
W przypadku małych liczb (3 lub 4, które są najczęściej spotykane), wiele pętli jest dość prostych i prostych. To niefortunne odpowiedzi, w których pętle nie zostały ocenione.
Zacznijmy od wyliczenia (zamiast permutacji). Po prostu przeczytaj kod jako kod pseudo Perla.
Wyliczenie jest częściej spotykane niż permutacja, ale jeśli potrzebna jest permutacja, po prostu dodaj warunki:
Teraz, jeśli naprawdę potrzebujesz ogólnej metody potencjalnie dla dużych list, możemy użyć metody radix. Najpierw rozważ problem wyliczenia:
Przyrost radix jest zasadniczo zliczaniem liczb (w podstawie liczby elementów listy).
Teraz, jeśli potrzebujesz permutacji, po prostu dodaj sprawdzenia wewnątrz pętli:
Edycja: powyższy kod powinien działać, ale w przypadku permutacji radix_increment może być marnotrawstwem. Więc jeśli czas ma znaczenie praktyczne, musimy zmienić radix_increment na permute_inc:
Oczywiście teraz ten kod jest logicznie bardziej złożony, zostawię czytelnikowi ćwiczenie.
źródło
Źródła : Geeksforgeeks.org
źródło
Jeśli ktoś się zastanawia jak to zrobić w permutacji w javascript.
Pomysł / pseudokod
na przykład. „a” + permute (bc). permutą bc byłoby bc & cb. Teraz dodaj te dwa, aby uzyskać abc, acb. podobnie, wybierz b + permute (ac) będzie sprzyjać bac, bca ... i kontynuować.
teraz spójrz na kod
Nie spiesz się, aby to zrozumieć. Mam ten kod z ( pertumation w JavaScript )
źródło
Kolejny w Pythonie, nie jest na miejscu jak @ cdiggins, ale myślę, że jest łatwiejszy do zrozumienia
źródło
Myślałem o napisaniu kodu do uzyskania permutacji dowolnej liczby całkowitej dowolnego rozmiaru, tj. Podając liczbę 4567 otrzymujemy wszystkie możliwe permutacje do 7654 ... Więc pracowałem nad tym, znalazłem algorytm i ostatecznie zaimplementowałem go, tutaj to kod zapisany w „c”. Możesz go po prostu skopiować i uruchomić na dowolnym kompilatorze open source. Ale niektóre błędy czekają na debugowanie. Proszę docenić.
Kod:
źródło
Stworzyłem ten. oparte na badaniach zbyt permutacja (qwe, 0, qwe.length-1); Pamiętaj, że możesz to zrobić z cofaniem lub bez
źródło
Oto metoda Ruby z zabawkami, która działa w ten sposób
#permutation.to_a
, może być bardziej czytelna dla szalonych ludzi. Jest bardzo powolny, ale także 5 linii.źródło
Napisałem to rozwiązanie rekurencyjne w ANSI C. Każde wykonanie funkcji Permutate zapewnia jedną inną permutację, aż wszystkie zostaną ukończone. Zmienne globalne mogą być również używane do zmiennych faktów i liczb.
źródło
Wersja Java
Na przykład
wynik:
źródło
w PHP
źródło
Oto kod w Pythonie do wydrukowania wszystkich możliwych permutacji listy:
Użyłem algorytmu porządku leksykograficznego, aby uzyskać wszystkie możliwe permutacje, ale algorytm rekurencyjny jest bardziej wydajny. Możesz znaleźć kod algorytmu rekurencyjnego tutaj: Permutacje rekurencyjne w Pythonie
źródło
źródło
W Scala
źródło
to jest wersja Java do permutacji
źródło
Oto implementacja ColdFusion (wymaga CF10 ze względu na argument merge funkcji ArrayAppend ()):
Oparte na rozwiązaniu js firmy KhanSharp powyżej.
źródło
Wiem, że jest to bardzo stare i nawet nie na temat w dzisiejszym przepływie stosów, ale nadal chciałem wnieść przyjazną odpowiedź javascript z prostego powodu, że działa w Twojej przeglądarce.
Dodałem również
debugger
punkt przerwania dyrektywy, dzięki czemu można przejść przez kod (wymagany Chrome), aby zobaczyć, jak działa ten algorytm. Otwórz konsolę deweloperską w Chrome (F12
w systemie Windows lubCMD + OPTION + I
na Macu), a następnie kliknij „Uruchom fragment kodu”. Implementuje ten sam dokładny algorytm, który @WhirlWind przedstawił w swojej odpowiedzi.Twoja przeglądarka powinna wstrzymać wykonywanie przy
debugger
dyrektywie. SłużyF8
do kontynuowania wykonywania kodu.Przejdź przez kod i zobacz, jak to działa!
źródło
W poniższym rozwiązaniu Java wykorzystujemy fakt, że ciągi znaków są niezmienne, aby uniknąć klonowania zestawu wyników przy każdej iteracji.
Dane wejściowe będą ciągiem znaków, powiedzmy „abc”, a danymi wyjściowymi będą wszystkie możliwe permutacje:
Kod:
To samo podejście można zastosować do tablic (zamiast ciągu):
źródło
To moje rozwiązanie w Javie:
źródło
Nie można naprawdę mówić o rozwiązaniu problemu permultacji w rekurencji bez opublikowania implementacji w języku (dialekcie), który był pionierem tego pomysłu . Tak więc, aby uzyskać kompletność, oto jeden ze sposobów, które można wykonać w Scheme.
dzwoniąc
(permof (list "foo" "bar" "baz"))
otrzymamy:Nie będę wchodził w szczegóły algorytmu, ponieważ zostało to wystarczająco wyjaśnione w innych postach. Idea jest taka sama.
Jednak problemy rekurencyjne są znacznie trudniejsze do modelowania i myślenia w destrukcyjnych mediach, takich jak Python, C i Java, podczas gdy w Lisp lub ML można je zwięźle wyrazić.
źródło
Oto rozwiązanie rekurencyjne w PHP. Post WhirlWinda dokładnie opisuje logikę. Warto wspomnieć, że generowanie wszystkich permutacji przebiega w czasie silni, więc dobrym pomysłem może być użycie podejścia iteracyjnego.
Funkcja strDiff pobiera dwa łańcuchy
s1
is2
, i zwraca nowy ciąg zawierający wszystkos1
bez elementów ws2
(powielona materia). A więcstrDiff('finish','i')
=>'fnish'
(drugie „i” nie jest usuwane).źródło
Oto algorytm w R, na wypadek gdyby ktoś musiał unikać ładowania dodatkowych bibliotek, tak jak ja musiałem.
Przykładowe użycie:
źródło
źródło
To jest kod rekurencyjny dla java, chodzi o to, aby mieć przedrostek dodający resztę znaków:
Przykład:
Input = "ABC"; Wynik:
ABC ACB BAC BCA CAB CBA
źródło
str
wywołania rekurencyjnego, w przeciwnym razie nie zakończy się.Aby być kompletnym, C ++
...
źródło
Oto nierekurencyjne rozwiązanie w C ++, które zapewnia następną permutację w porządku rosnącym, podobnie do funkcjonalności zapewnianej przez std :: next_permutation:
źródło