Faktoradik: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
kTidak ada ringkasan suntingan |
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
| (23 revisi perantara oleh 16 pengguna tidak ditampilkan) | |||
Baris 1:
{{tanpa referensi}}
'''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''<sub>n</sub>...''a''<sub>4</sub>''a''<sub>3</sub>''a''<sub>2</sub>''a''<sub>1</sub>''a''<sub>0</sub>, dengan setiap bilangan ''a''<sub>i</sub> bersifat:
:<math>a_i \in \mathbb{N}</math>
dan
:<math>0 \leq a_i \leq i</math>
== Nilai faktoradik ==
Nilai sebuah faktoradik ''a''<sub>n</sub>...''a''<sub>4</sub>''a''<sub>3</sub>''a''<sub>2</sub>''a''<sub>1</sub>''a''<sub>0</sub> dapat dengan mudah didapat menggunakan formula:
:<math>\sum_{i=0}^n a_i.i! </math>
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
Baris 43 ⟶ 49:
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 <math>n</math> dengan algoritme sebagai berikut:
# Cari <math>i !</math> terbesar di mana <math>i ! < n</math>
# Bagi <math>n</math> dengan <math>i !</math>, akan didapatkan hasil bagi <math>d</math> dan sisa bagi <math>m</math>.
# <math>d</math> adalah digit faktoradik ke-<math>i</math>, yaitu <math>a_i</math>
# Ulangi dari langkah kedua, dengan <math>m</math>(sisa bagi) menggantikan <math>n</math>, dan <math>i - 1</math> menggantikan <math>i</math>.
# Algoritme selesai jika <math>i</math> sudah mencapai 0.
Ketika berakhir, algoritme ini akan menghasilkan deretan faktoradik ''a''<sub>n</sub>...''a''<sub>4</sub>''a''<sub>3</sub>''a''<sub>2</sub>''a''<sub>1</sub>''a''<sub>0</sub>.
== 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 <math>s</math>, dan sebuah faktoradik <math>f</math>, maka algoritme untuk menghasilkan sebuah permutasi dari <math>s</math> adalah:
# Sediakan satu tempat, yaitu <math>s'</math> untuk menampung untai hasil permutasi
# Mulai dari digit <math>f</math> paling kiri (digit dengan indeks posisi paling besar):
#* Ambil huruf dari <math>s</math> di posisi <math>f_i</math>, pindahkan ke <math>s'</math>
# Ulangi hingga tidak ada lagi huruf pada untai <math>s</math>
Ketika algoritme ini selesai, <math>s'</math> akan merupakan permutasi dari <math>s</math> yang sesuai dengan <math>f</math>
Sebagai contoh, untuk menghasilkan permutasi dari '''abcdefg''', dengan indeks faktoradik 5341200 dengan algoritme tersebut, diberikan:
:<math>s = \mathbf{abcdefg}</math>
dan
:<math>f = (5, 3, 4, 1, 2, 0, 0)</math>
Disediakan <math>s' = \epsilon</math> (masih kosong).
:{| class="wikitable"
|-
| Untai
| a
| b
| c
| d
| e
| f
| g
|-
| Indeks
| 0
| 1
| 2
| 3
| 4
| 5
| 6
|}
Pertama, mulai dari <math>f_6</math>, yaitu 5. Kemudian pindahkan huruf ke-5 (indeks 5) pada untai <math>s</math> ke untai <math>s'</math>, yaitu huruf '''f'''. Kondisi <math>s</math> dan <math>s'</math> sekarang menjadi <math>s = \mathbf{abcdeg}</math> dan <math>s' = \mathbf{f}</math>
Dengan <math>s</math> sekarang menjadi:
:{| class="wikitable"
|-
| Untai
| a
| b
| c
| d
| e
| g
|-
| Indeks
| 0
| 1
| 2
| 3
| 4
| 5
|}
Bilangan kedua dari <math>f</math>, yaitu <math>f_5</math> adalah 3, maka pindahkan huruf ke-3 pada untai <math>s</math> ke untai <math>s'</math>. Maka kondisinya menjadi <math>s = \mathbf{abceg}</math> dan <math>s' = \mathbf{fd}</math>
:{| 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
! <math>f_i</math>
! <math>s</math>
! <math>s'</math>
|-
| 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 ==
[http://msdn2.microsoft.com/en-us/library/aa302371.aspx Using Permutations in .NET for Improved Systems Security] {{Webarchive|url=https://web.archive.org/web/20080412030829/http://msdn2.microsoft.com/en-us/library/aa302371.aspx |date=2008-04-12 }}
[[Kategori:Sistem bilangan]]
[[Kategori:Kombinatorika]]
| |||