Permutations

Rozbudowuj uporządkowania po jednej wartości. Gdy nie ma żadnych wartości, istnieje jedno uporządkowanie: pusta lista. Aby dodać wartość 3 do uporządkowania [1, 2], umieść ją w każdej z jego trzech luk: [3, 1, 2], [1, 3, 2] i [1, 2, 3]. Zrób to dla każdego uporządkowania, które masz, a uporządkowania k wartości przekształcą się w uporządkowania k+1 wartości.

Każde uporządkowanie k+1 wartości powstaje dokładnie raz: usuń z niego najnowszą wartość, a otrzymasz jedyne uporządkowanie, z którego powstało, natomiast pozycja najnowszej wartości wskazuje lukę. Liczby te wynoszą więc 1, 2, 6, 24, a n wartości daje n! uporządkowań.

Nie powstają one w wymaganej kolejności. Dla [1, 2, 3] pierwszym utworzonym uporządkowaniem jest [3, 2, 1], więc na końcu trzeba je posortować, porównując pozycje jedna po drugiej. To sortowanie jest kosztowną częścią: n! uporządkowań wymaga około n! × log(n!) porównań, a każde z nich odczytuje do n wartości. Dla sześciu wartości to w przybliżeniu 720 × 9.5 × 6, czyli około 41 000 odczytów. Podczas tworzenia kolejnej generacji metoda przechowuje też w pamięci całą poprzednią generację uporządkowań.

Wypełnij n miejsc od lewej do prawej. Pierwsze miejsce ma n kandydatów, drugie n-1 i tak dalej — stąd bierze się n!. Przedstaw te wybory jako drzewo: korzeń to pusta ścieżka, każda krawędź dodaje jedną wartość, a każdy liść na głębokości n to jedno gotowe uporządkowanie. Dla posortowanych wartości 1, 2, 3 korzeń ma dzieci [1], [2] i [3]; [1] ma dzieci [1, 2] i [1, 3]; każde z nich ma po jednym liściu.

Wycofywanie przechodzi przez to drzewo, korzystając z jednej współdzielonej ścieżki path i flagi used dla każdej wartości. W każdym węźle pętla przechodzi przez wartości i pomija te, które są już użyte. Dla każdej dostępnej wartości wykonuje wybór (oznacza ją jako używaną i dodaje do ścieżki), eksplorację (rekurencyjnie przechodzi poziom głębiej), a następnie cofa wybór (usuwa ją i oznacza jako dostępną). Cofnięcie wyboru przywraca dokładnie stan sprzed pętli, więc następna wartość jest sprawdzana w tym samym węźle. Ścieżka o długości n jest liściem: zapisz jej kopię i wróć.

Kolejność uzyskuje się sama. Pętla najpierw próbuje najmniejszą dostępną wartość, a przejście kończy wszystkie uporządkowania zaczynające się od danego prefiksu, zanim zmieni ten prefiks. Zatem wszystkie uporządkowania zaczynające się od 1 pojawiają się przed tymi zaczynającymi się od 2, a wśród nich [1, 2, ...] pojawia się przed [1, 3, ...]. To kolejność leksykograficzna. Dlatego najpierw sortujesz też nums: pętla przechodzi po indeksach, więc indeksy muszą być uporządkowane według wartości.

Drzewo ma około e × n! węzłów (e wynosi około 2.72), a każdy z nich wykonuje pętlę n razy, więc złożoność czasowa wynosi O(n × n!), czyli tyle samo co rozmiar wyniku. Poza wynikiem ścieżka, flagi i stos wywołań przechowują najwyżej po n elementów.