Istnieje wiele algorytmów generowania wszystkich możliwych permutacji zbioru N-elementowego. Najlepsze z nich wymagają N!-1 zamian miejscami elementów zbioru. Są one jednak znacznie mniej przejrzyste od prostego algorytmu, który przedstawimy poniżej. Algorytm ten, zaczerpnięty z wykładu R. Sedgewicka na Uniwersytecie w Princeton wymaga 2N! zamian i jest przykładem algorytmu z powrotami.
Będziemy permutować tablicę liczb naturalnych P:
P[] = {1, 2, 3, …, N}
Funkcja permutująca ma następującą postać:
perm(k)
if k==1
print P
else
for i=1 to k do
swap P[i]↔P[k]
perm(k-1)
swap P[i]↔P[k]
Uruchomienie całego algorytmu następuje poprzez wywołanie funkcji perm(N).
Jak to działa? Prześledźmy we fragmencie przebieg algorytmu dla N=3. Na początku mamy:
P={1,2,3}
perm(3)
Wykonywana jest pętla po i – dla i=1 mamy:
swap P[1]↔P[3] // P={3,2,1}
perm(2)
W tej instancji funkcji perm także wykonywana jest pętla po i – dla i=1 mamy:
swap P[1]↔P[2] // P={2,3,1}
perm(1) // wypisywana jest powyższa permutacja
swap P[1]↔P[2] // P={3,2,1}
Dla i=2 mamy:
swap P[2]↔P[2] // P={3,2,1}
perm(1) // wypisywana jest powyższa permutacja
swap P[2]↔P[2] // P={3,2,1}
Wypisaliśmy wszystkie permutacje z elementem 1 na końcu. Na tym kończy się działanie tej instancji funkcji perm(2), wracamy zatem do funkcji perm(3). Kolejna instrukcja swap przywraca naturalną kolejność w tablicy P: {1,2,3}, przechodzimy do kolejnej wartości zmiennej i, po czym w analogiczny sposób generujemy pozostałe permutacje.
Powrót do Algorytmy wykładnicze