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₄a₃a₂a₁a₀, 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₄a₃a₂a₁a₀ 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.

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 Bilangan

Suatu faktoradik bisa diperoleh dari sembarang bilangan $n$ dengan algoritme 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 $a_{i}$
Ulangi dari langkah kedua, dengan $m$ (sisa bagi) menggantikan $n$ , dan $i-1$ menggantikan $i$ .
Algoritme selesai jika $i$ sudah mencapai 0.

Ketika berakhir, algoritme ini akan menghasilkan deretan faktoradik a_n...a₄a₃a₂a₁a₀.

Permutasi

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 algoritme 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 algoritme ini selesai, $s'$ akan merupakan permutasi dari $s$ yang sesuai dengan $f$

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

s=\mathbf {abcdefg}

dan

f=(5,3,4,1,2,0,0)

Disediakan $s'=\epsilon$ (masih kosong).

Untai	a	b	c	d	e	f	g
Indeks	0	1	2	3	4	5	6

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:

Untai	a	b	c	d	e	g
Indeks	0	1	2	3	4	5

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}$

Untai	a	b	c	e	g
Indeks	0	1	2	4	6

Dan seterusnya, yang jika dituliskan sekaligus adalah seperti ini:

i	$f_{i}$	$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

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

Pranala luar

Using Permutations in .NET for Improved Systems Security Diarsipkan 2008-04-12 di Wayback Machine.