Generowanie wszystkich permutacji

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

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License