Faktoradik
Dari Wikipedia Indonesia, ensiklopedia bebas berbahasa Indonesia.
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
Daftar isi |
[sunting] Nilai faktoradik
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
[sunting] Mendapatkan Faktoradik dari Sembarang Bilangan
Suatu faktoradik bisa diperoleh dari sembarang bilangan n dengan algoritma sebagai berikut:
- Cari i! terbesar di mana i! < n
- Bagi n dengan i!, akan didapatkan hasil bagi d dan sisa bagi m.
- d adalah digit faktoradik ke-i, yaitu ai
- Ulangi dari langkah kedua, dengan m(sisa bagi) menggantikan n, dan i − 1 menggantikan i.
- Algoritma selesai jika i sudah mencapai 0.
Ketika berakhir, algoritma ini akan menghasilkan deretan faktoradik an...a4a3a2a1a0.
[sunting] Permutasi
[sunting] Bilangan Inversi
[sunting] Membentuk Permutasi berdasarkan Faktoradik
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 s, dan sebuah faktoradik f, maka algoritma untuk menghasilkan sebuah permutasi dari s adalah:
- Sediakan satu tempat, yaitu s' untuk menampung untai hasil permutasi
- Mulai dari digit f paling kiri (digit dengan indeks posisi paling besar):
- Ambil huruf dari s di posisi fi, pindahkan ke s'
- Ulangi hingga tidak ada lagi huruf pada untai s
Ketika algoritma ini selesai, s' akan merupakan permutasi dari s yang sesuai dengan f
Sebagai contoh, untuk menghasilkan permutasi dari abcdefg, dengan indeks faktoradik 5341200 dengan algoritma tersebut, diberikan:
dan
- f = (5,3,4,1,2,0,0)
Disediakan s' = ε (masih kosong).
-
Untai a b c d e f g Indeks 0 1 2 3 4 5 6
Pertama, mulai dari f6, yaitu 5. Kemudian pindahkan huruf ke-5 (indeks 5) pada untai s ke untai s', yaitu huruf f. Kondisi s dan s' sekarang menjadi
dan 
Dengan s sekarang menjadi:
-
Untai a b c d e g Indeks 0 1 2 3 4 5
Bilangan kedua dari f, yaitu f5 adalah 3, maka pindahkan huruf ke-3 pada untai s ke untai s'. 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 fi s s' 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
[sunting] Kode-kode program
[sunting] Kode program untuk membangkitkan faktoradik
[sunting] Pascal
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;
[sunting] Kode untuk membangkitkan permutasi dari faktoradik
[sunting] Pascal
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;
[sunting] Lihat Juga
- Kombinadik
- Permutasi
- Bilangan Inversi
- Sistem bilangan





