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
*a*n...*a*4*a*3*a*2*a*1*a*0, dengan setiap bilangan *a*i bersifat:

:a_i \in \mathbb{N}

dan

:0 \leq a_i \leq i

## Nilai faktoradik
Nilai sebuah faktoradik *a*n...*a*4*a*3*a*2*a*1*a*0 dapat dengan mudah didapat menggunakan formula:

:\sum_{i=0}^n a_i.i! 

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.
:

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:
:

## Mendapatkan Faktoradik dari Sembarang Bilangan
Suatu faktoradik bisa diperoleh dari sembarang bilangan n dengan algoritma sebagai berikut:

# Cari i ! terbesar di mana i ! 
# Bagi n dengan i !, akan didapatkan hasil bagi d dan sisa bagi m.
# d adalah digit faktoradik ke-i, yaitu a_i
# 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 *a*n...*a*4*a*3*a*2*a*1*a*0.

## Permutasi
### Membentuk Permutasi berdasarkan Faktoradik
Pertama-tama kita harus membuat kesepakatan mengenai indeks. Indeks untuk untai dimulai dengan indeks 0 dari kiri.
:
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 f_i, 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:

:s = \mathbf{abcdefg}
dan
:f = (5, 3, 4, 1, 2, 0, 0)

Disediakan s' = \epsilon (masih kosong).

:

Pertama, mulai dari f_6, yaitu 5. Kemudian pindahkan huruf ke-5 (indeks 5) pada untai s ke untai s', yaitu huruf **f**. Kondisi s dan s' sekarang menjadi s = \mathbf{abcdeg} dan s' = \mathbf{f}

Dengan s sekarang menjadi:

:

Bilangan kedua dari f, yaitu f_5 adalah 3, maka pindahkan huruf ke-3 pada untai s ke untai s'. Maka kondisinya menjadi s = \mathbf{abceg} dan s' = \mathbf{fd}

:

Dan seterusnya, yang jika dituliskan sekaligus adalah seperti ini:
:

## 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