Faktoradik: Perbedaan antara revisi

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Konten dihapus Konten ditambahkan
Xqbot (bicara | kontrib)
ArthurBot (bicara | kontrib)
k r2.6.3) (bot Menambah: hu:Faktoriális számrendszer
Baris 320: Baris 320:
[[en:Factorial number system]]
[[en:Factorial number system]]
[[es:Factorádico]]
[[es:Factorádico]]
[[hu:Faktoriális számrendszer]]
[[nl:Faculteitssysteem]]
[[nl:Faculteitssysteem]]
[[pl:Silniowy system pozycyjny]]
[[pl:Silniowy system pozycyjny]]

Revisi per 23 Februari 2011 11.35

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.

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 dengan algoritma 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. Algoritma selesai jika sudah mencapai 0.

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

Permutasi

Bilangan Inversi

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 , dan sebuah faktoradik , maka algoritma 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 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).

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