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
.
Hendak dibuat himpunan
.
 Jika s tidak kosong, maka untuk setiap abjad untai s (a0 hingga an), yaitu ai:
 Pindahkan ai ke p (taruh paling belakang).
 Jalankan algoritma kembali untuk s dan p yang baru.
 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''';

 Lihat pula 
 Permutasi
 Permutadik

Kategori:Algoritme
Kategori:Kombinatorika