Buka menu utama

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

Nilai faktoradikSunting

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

Mendapatkan Faktoradik dari Sembarang BilanganSunting

Suatu faktoradik bisa diperoleh dari sembarang bilangan   dengan algoritme sebagai berikut:

  1. Cari   terbesar di mana  
  2. Bagi   dengan  , akan didapatkan hasil bagi   dan sisa bagi  .
  3.   adalah digit faktoradik ke- , yaitu  
  4. Ulangi dari langkah kedua, dengan  (sisa bagi) menggantikan  , dan   menggantikan  .
  5. Algoritme selesai jika   sudah mencapai 0.

Ketika berakhir, algoritme ini akan menghasilkan deretan faktoradik an...a4a3a2a1a0.

PermutasiSunting

Membentuk Permutasi berdasarkan FaktoradikSunting

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:

  1. Sediakan satu tempat, yaitu   untuk menampung untai hasil permutasi
  2. Mulai dari digit   paling kiri (digit dengan indeks posisi paling besar):
    • Ambil huruf dari   di posisi  , pindahkan ke  
  3. Ulangi hingga tidak ada lagi huruf pada untai  

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

Kode-kode programSunting

Kode program untuk membangkitkan faktoradikSunting

PascalSunting

 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;

Kode untuk membangkitkan permutasi dari faktoradikSunting

PascalSunting

 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;

Lihat pulaSunting

Pranala luarSunting