Faktoradik

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 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.
{| class="wikitable"
|-
| 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:
{| class="wikitable"
|-
! 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 Bilangan 
Suatu faktoradik bisa diperoleh dari sembarang bilangan  dengan algoritma sebagai berikut:

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

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

 Permutasi 
 Membentuk Permutasi berdasarkan Faktoradik 
Pertama-tama kita harus membuat kesepakatan mengenai indeks. Indeks untuk untai dimulai dengan indeks 0 dari kiri.
{| class="wikitable"
|-
| Untai
| a
| b
| c
| d
| e
| f
| g
|-
| Indeks
| 0
| 1
| 2
| 3
| 4
| 5
| 6
|}
Disediakan sebuah untai , dan sebuah faktoradik , maka algoritma untuk menghasilkan sebuah permutasi dari  adalah:
 Sediakan satu tempat, yaitu  untuk menampung untai hasil permutasi
 Mulai dari digit  paling kiri (digit dengan indeks posisi paling besar):
 Ambil huruf dari  di posisi , pindahkan ke 
 Ulangi hingga tidak ada lagi huruf pada untai 
Ketika algoritma ini selesai,  akan merupakan permutasi dari  yang sesuai dengan 

Sebagai contoh, untuk menghasilkan permutasi dari abcdefg, dengan indeks faktoradik 5341200 dengan algoritma tersebut, diberikan:

dan

Disediakan  (masih kosong).

{| class="wikitable"
|-
| 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:

{| class="wikitable"
|-
| 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 

{| class="wikitable"
|-
| Untai
| a
| b
| c
| e
| g
|-
| Indeks
| 0
| 1
| 2
| 4
| 6
|}

Dan seterusnya, yang jika dituliskan sekaligus adalah seperti ini:
{| class="wikitable"
! 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 program 
 Kode program untuk membangkitkan faktoradik 
 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;

 Kode untuk membangkitkan permutasi dari faktoradik 
 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;

 Lihat pula 
 Kombinadik
 Permutasi
 Bilangan Inversi
 Sistem bilangan

 Pranala luar 
Using Permutations in .NET for Improved Systems Security 

Kategori:Sistem bilangan
Kategori:Kombinatorika