Częstym zadaniem w programowaniu wywiadów (choć nie z mojego doświadczenia w wywiadach) jest branie łańcucha lub liczby całkowitej i lista wszystkich możliwych permutacji.
Czy istnieje przykład, jak to się robi i logika rozwiązania takiego problemu?
Widziałem kilka fragmentów kodu, ale nie zostały one dobrze skomentowane / wyjaśnione, a przez to trudne do naśladowania.
c#
algorithm
permutation
GurdeepS
źródło
źródło
Odpowiedzi:
Po pierwsze: oczywiście pachnie rekurencją !
Ponieważ chciałeś również poznać zasadę, zrobiłem wszystko, co w mojej mocy, aby wyjaśnić to ludzkim językiem. Myślę, że rekurencja jest bardzo łatwa w większości przypadków. Musisz tylko wykonać dwa kroki:
W języku ludzkim :
Znalazłem pseudokod na http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/ :
DO#
OK, i coś bardziej rozbudowanego (a ponieważ jest oznaczony jako c #), z http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : Raczej długi, ale zdecydowałem się go skopiować zresztą post nie jest zależny od oryginału.
ABC, ACB, BAC, BCA, CAB, CBA.
Kod:
źródło
Swap(ref list[k], ref list[i]);
) jest niepotrzebna.(a[x], a[y]) = (a[y], a[x]);
To tylko dwa wiersze kodu, jeśli LINQ może używać. Zobacz moją odpowiedź tutaj .
EDYTOWAĆ
Oto moja ogólna funkcja, która może zwrócić wszystkie permutacje (nie kombinacje) z listy T:
Przykład:
Wyjście - lista list całkowitych:
Ponieważ ta funkcja korzysta z LINQ, wymaga .net 3.5 lub nowszej.
źródło
const string s = "HALLOWEEN";
var result = GetPermutations(Enumerable.Range(0, s.Length), s.Length).Select(t => t.Select(i => s[i]));
Tutaj znalazłem rozwiązanie. Został napisany w Javie, ale przekonwertowałem go na C #. Mam nadzieję, że ci to pomoże.
Oto kod w C #:
źródło
Rekursja nie jest konieczna, oto dobre informacje na temat tego rozwiązania.
Używam tego algorytmu od lat, ma on czas i przestrzeń O (N) złożoność aby obliczyć każdą permutację .
źródło
O(N-1)
dla sekwencji iO(N)
zamiany, czyliO(N)
. I nadal używam tego w produkcji, ale z refaktorem do generowania tylko jednej permutacji, na przykład:GetPermutation(i)
gdzie0 <= i <= N!-1
. Z przyjemnością użyję czegoś o lepszej wydajności niż ta, więc możesz swobodnie wywołać odniesienie dla czegoś lepszego, większość alternatyw używa sięO(N!)
w pamięci, więc możesz to również sprawdzić.Możesz napisać swoją funkcję swap, aby zamieniać znaki.
To ma być nazwane jako permute (string, 0);
źródło
Po pierwsze, zestawy mają permutacje, a nie łańcuchy lub liczby całkowite, więc przyjmuję, że masz na myśli „zestaw znaków w ciągu”.
Zauważ, że zbiór o rozmiarze n ma n! n-permutacje.
Poniższy pseudokod (z Wikipedii), wywołany z k = 1 ... n! poda wszystkie permutacje:
Oto równoważny kod w Pythonie (dla indeksów tablic opartych na 0):
źródło
k := k / j;
robi.Nieznacznie zmodyfikowana wersja w C #, która daje potrzebne permutacje w tablicy dowolnego typu.
źródło
Permutations(vals).ToArray()
otrzymasz N odniesień do tej samej tablicy. Jeśli chcesz mieć możliwość przechowywania wyników, musisz ręcznie utworzyć kopię. Np.Permutations(values).Select(v => (T[])v.Clone())
źródło
Podobało mi się podejście FBryant87, ponieważ jest proste. Niestety, podobnie jak wiele innych „rozwiązań” nie oferuje wszystkich permutacji lub np. Liczby całkowitej, jeśli zawiera tę samą cyfrę więcej niż raz. Weźmy jako przykład 656123. Linia:
stosując wyjątkiem spowoduje wszystkie wystąpienia być usunięty, to znaczy gdy c = 6, dwie cyfry są usuwane, a my zostajemy z np 5123. Ponieważ żaden z rozwiązań Próbowałem rozwiązać ten, postanowiłem spróbować rozwiązać go samodzielnie przez FBryant87 S” kod jako podstawa. Oto, co wymyśliłem:
Po prostu usuwam pierwsze znalezione wystąpienie za pomocą .Remove i .IndexOf. Wygląda na to, że przynajmniej działa zgodnie z przeznaczeniem. Jestem pewien, że można by to uczynić mądrzejszym.
Należy jednak zwrócić uwagę na jedną rzecz: wynikowa lista może zawierać duplikaty, więc upewnij się, że metoda zwraca np. Zestaw HashSet lub usuwasz duplikaty po powrocie przy użyciu dowolnej metody.
źródło
Oto dobry artykuł obejmujący trzy algorytmy do znajdowania wszystkich permutacji, w tym jeden do znajdowania następnej permutacji.
http://www.cut-the-knot.org/do_you_know/AllPerm.shtml
C ++ i Python mają odpowiednio wbudowane funkcje next_permutation i itertools.permutations .
źródło
Oto czysto funkcjonalna implementacja języka F #:
Wydajność można znacznie poprawić, zmieniając zamianę, aby wykorzystać zmienną naturę tablic CLR, ale ta implementacja jest bezpieczna wątkowo w odniesieniu do tablicy źródłowej i może być pożądana w niektórych kontekstach. Ponadto w przypadku tablic zawierających więcej niż 16 elementów int należy zastąpić typami o większej / arbitralnej precyzji, ponieważ silnia 17 powoduje przepełnienie int32.
źródło
Oto proste rozwiązanie w języku C # przy użyciu rekurencji,
źródło
Oto łatwa do zrozumienia funkcja permutaion dla łańcucha i liczby całkowitej jako danych wejściowych. Dzięki temu możesz nawet ustawić długość wyjściową (która w normalnym przypadku jest równa długości wejściowej)
Strunowy
a dla Integer po prostu zmień metodę caller, a MakePermutations () pozostanie nietknięta:
przykład 1: GetAllPermutations ("abc", 3); "abc" "acb" "bac" "bca" "cab" "cba"
przykład 2: GetAllPermutations ("abcd", 2); "ab" "ac" "ad" "ba" "bc" "bd" "ca" "cb" "cd" "da" "db" "dc"
przykład 3: GetAllPermutations (486,2); 48 46 84 86 64 68
źródło
Oto funkcja, która wypisze całą permutację. Ta funkcja implementuje logikę wyjaśnioną przez petera.
źródło
Poniżej znajduje się moja implementacja permutacji. Nie przejmuj się nazwami zmiennych, bo robiłem to dla przyjemności :)
źródło
Oto przykład wysokiego poziomu, który napisałem, który ilustruje wyjaśnienie języka ludzkiego podane przez Piotra:
źródło
Jeśli problemem jest wydajność i pamięć, proponuję tę bardzo wydajną implementację. Według algorytmu Heapa w Wikipedii powinien on być najszybszy. Mam nadzieję, że będzie pasował do Twoich potrzeb :-)!
Podobnie jak porównanie tego z implementacją Linq dla 10! (zawiera kod):
Linq: 36288000 elementów w 50051 milisekundach
źródło
Oto moje rozwiązanie w JavaScript (NodeJS). Główną ideą jest to, że bierzemy po jednym elemencie na raz, "usuwamy go" z łańcucha, zmieniamy pozostałe znaki i wstawiamy element z przodu.
A oto testy:
źródło
Oto najprostsze rozwiązanie, jakie przychodzi mi do głowy:
distribute
Funkcja przyjmuje nowego elementue
orazn
listy -elementowe i zwraca listęn+1
list z których każdy mae
włożonych w innym miejscu. Na przykład wstawianie10
w każdym z czterech możliwych miejsc na liście[1;2;3]
:permute
Funkcja fałdy nad każdym elementem z kolei nad dystrybucją permutacji zgromadzone do tej pory, zakończonego we wszystkich permutacji. Na przykład 6 permutacji listy[1;2;3]
:Zmiana na
fold
ascan
w celu zachowania akumulatorów pośrednich rzuca trochę światła na to, jak permutacje są generowane po jednym elemencie:źródło
Wyświetla permutacje ciągu. Pozwala uniknąć powielania, gdy znaki się powtarzają:
źródło
Opierając się na rozwiązaniu @ Peter, oto wersja, która deklaruje prostą
Permutations()
metodę rozszerzenia w stylu LINQ, która działa na dowolnymIEnumerable<T>
.Użycie (na przykładzie znaków ciągu):
Wyjścia:
Lub w przypadku każdego innego rodzaju kolekcji:
Wyjścia:
źródło
Oto funkcja, która wypisze rekursywnie wszystkie permutacje.
źródło
źródło
Oto odpowiedź w języku C #, która jest nieco uproszczona.
Wynik:
źródło
To jest moje rozwiązanie, które jest dla mnie łatwe do zrozumienia
źródło
Oto jeszcze jedna implementacja wspomnianego algo.
źródło
new Permutation().GenerateFor("aba")
wyjściastring[4] { "ab", "baa", "baa", "ab" }
źródło
źródło