Faktoradik adalah sebuah sistem bilangan yang setiap posisi angka memiliki basis sesuai dengan faktorial dari posisinya. Sistem bilangan ini memungkinkan untuk membangkitkan permutasi dalam urutan leksikografik.
Faktoradik memiliki bentuk deretan bilangan an...a4a3a2a1a0, dengan setiap bilangan ai bersifat:
dan
Nilai sebuah faktoradik an...a4a3a2a1a0 dapat dengan mudah didapat menggunakan formula:
Sebagai contoh, bilangan 2,1,1,1,0
Posisi setiap bilangan, sama seperti pada sistem bilangan posisional lainnya, dinomori mulai dari 0 dari sebelah kanan.
Bilangan ke | 5 | 4 | 3 | 2 | 1 | 0 |
Bilangan | 0 | 2 | 1 | 1 | 1 | 0 |
Faktorial | 120 | 24 | 6 | 2 | 1 | 1 |
Sehingga nilainya adalah sebesar: 2×4! + 1×3! + 1×2! + 1×1! + 0×0! = 57
Di bawah ini adalah daftar 24 faktoradik pertama beserta nilainya:
Faktoradik | Nilai | Faktoradik | Nilai | Faktoradik | Nilai | Faktoradik | Nilai |
---|---|---|---|---|---|---|---|
0, 0, 0, 0 | 0 | 1, 0, 0, 0 | 6 | 2, 0, 0, 0 | 12 | 3, 0, 0, 0 | 18 |
0, 0, 1, 0 | 1 | 1, 0, 1, 0 | 7 | 2, 0, 1, 0 | 13 | 3, 0, 1, 0 | 19 |
0, 1, 0, 0 | 2 | 1, 1, 0, 0 | 8 | 2, 1, 0, 0 | 14 | 3, 1, 0, 0 | 20 |
0, 1, 1, 0 | 3 | 1, 1, 1, 0 | 9 | 2, 1, 1, 0 | 15 | 3, 1, 1, 0 | 21 |
0, 2, 0, 0 | 4 | 1, 2, 0, 0 | 10 | 2, 2, 0, 0 | 16 | 3, 2, 0, 0 | 22 |
0, 2, 1, 0 | 5 | 1, 2, 1, 0 | 11 | 2, 2, 1, 0 | 17 | 3, 2, 1, 0 | 23 |
Suatu faktoradik bisa diperoleh dari sembarang bilangan dengan algoritme sebagai berikut:
Ketika berakhir, algoritme ini akan menghasilkan deretan faktoradik an...a4a3a2a1a0.
Pertama-tama kita harus membuat kesepakatan mengenai indeks. Indeks untuk untai dimulai dengan indeks 0 dari kiri.
Untai | a | b | c | d | e | f | g |
Indeks | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Disediakan sebuah untai , dan sebuah faktoradik , maka algoritme untuk menghasilkan sebuah permutasi dari adalah:
Ketika algoritme ini selesai, akan merupakan permutasi dari yang sesuai dengan
Sebagai contoh, untuk menghasilkan permutasi dari abcdefg, dengan indeks faktoradik 5341200 dengan algoritme tersebut, diberikan:
dan
Disediakan (masih kosong).
Untai | a | b | c | d | e | f | g |
Indeks | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Pertama, mulai dari , yaitu 5. Kemudian pindahkan huruf ke-5 (indeks 5) pada untai ke untai , yaitu huruf f. Kondisi dan sekarang menjadi dan
Dengan sekarang menjadi:
Untai | a | b | c | d | e | g |
Indeks | 0 | 1 | 2 | 3 | 4 | 5 |
Bilangan kedua dari , yaitu adalah 3, maka pindahkan huruf ke-3 pada untai ke untai . Maka kondisinya menjadi dan
Untai | a | b | c | e | g |
Indeks | 0 | 1 | 2 | 4 | 6 |
Dan seterusnya, yang jika dituliskan sekaligus adalah seperti ini:
i | |||
---|---|---|---|
6 | 5 | abcdeg | f |
5 | 3 | abceg | fd |
4 | 4 | abce | fdg |
3 | 1 | ace | fdgb |
2 | 2 | ac | fdgbe |
1 | 0 | c | fdgbea |
0 | 0 | fdgbeac |
FMax:= CariFaktorialTerbesar(Bilangan); Sisa:= Bilangan; for i:= FMax downto 0 do begin f:= Faktorial(i); A[i]:= Sisa div f; Sisa:= Sisa mod f; end;
function Permutasi(Untai: STRING; Faktoradik: array of INTEGER): STRING; var Hasil: STRING; i, Indeks: INTEGER; begin Hasil:=; for i:=Low(Faktoradik) to High(Faktoradik) do begin Indeks:=Faktoradik[i] + 1; // Indeks ditambah 1 karena indeks array berawal dari 0 Hasil:=Hasil + Untai[ Indeks ]; Delete(Untai, Indeks, 1); end; Permutasi:=Hasil; end;
Using Permutations in .NET for Improved Systems Security Diarsipkan 2008-04-12 di Wayback Machine.