Membangkitkan Permutasi | Wiki eduNitas, Kumpulan Ensiklopedi Dunia

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$ .

Hendak dibuat himpunan

$P(s) = { p_i,|, p_i mbox{ adalah permutasi ke-}imbox{ 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;

Sumber :
wiki.kpt.co.id, id.wikipedia.org, buku.us, dsb.