Membangkitkan Permutasi

Membangkitkan Permutasi berarti membentuk untai S' yang merupakan permutasi dari untai S.

Permasalahan umum yang terdapat seputar membangkitkan permutasi adalah:

Diberikan sebuah untai S, tentukan:

Semua permutasi dari S
Semua permutasi n-elemen dari S
Permutasi berikutnya setelah S
Permutasi ke-k dari s sesuai urutan leksikografik (atau aturan lainnya)

Membangkitkan seluruh permutasi dari S

Menggunakan rekursi

Kita dapat mendaftar semua himpunan permutasi dari S dengan algoritma sebagai berikut:

Diberikan sebuah untai

s = a 0 a 1 a 2 . . . a n − 1 a n {\displaystyle s=a_{0}\,a_{1}\,a_{2}\,...\,a_{n-1}\,a_{n}} $s=a_{0}\,a_{1}\,a_{2}\,...\,a_{n-1}\,a_{n}$ .

Hendak dibuat himpunan

P ( s ) = { p i | p i adalah permutasi ke- i dari s } {\displaystyle P(s)=\{p_{i}\,|\,p_{i}{\mbox{ adalah permutasi ke-}}i{\mbox{ dari }}s\}} $P(s)=\{p_{i}\,|\,p_{i}{\mbox{ adalah permutasi ke-}}i{\mbox{ dari }}s\}$ .

Jika s tidak kosong, maka untuk setiap abjad untai s (a₀ hingga a_n), yaitu a_i:
1. Pindahkan a_i ke p (taruh paling belakang).
2. Jalankan algoritma kembali untuk s dan p yang baru.
3. Kembalikan huruf yang telah dipindahkan ke posisi semula.
Jika s sudah kosong, maka p adalah sebuah permutasi dari s.

Implementasi algoritma tersebut dalam bahasa Pascal adalah seperti yang tertulis di bawah ini. Prosedur ini akan mencetak semua kemungkinan permutasi.

 procedure perm(s, p: string);
 begin
   if' s <> ''  then
   begin
     for i:= 1 to length(s) do
     begin
       // pindahkan abjad ke-i dari s ke p
       p:= p + s[i];
       delete(s, i, 1);
 
       perm(s, p);
 
       // kembalikan abjad yang telah diambil ke posisi semula
       insert(p[length(p)], s, 1);
       delete(p, length(p), 1);
     end;
   end
   else
     writeln(p);
 end;