PERBANDINGAN ENUMERASI PERMUTASI N DENGAN 2 SIKLUS BERDASARKAN RUMUSAN BILANGAN STIRLING DENGAN RUMUSAN SULISTYO Meta Meysawati e-mail :
[email protected] Jurusan Teknik Informatika Universitas Gunadarma Jl Margonda 100
ABSTRAK Enumerasi adalah menghitung banyak objek pada suatu objek kombinatorik. Kombinatorik merupakan ilmu yang mempelajari sifat-sifat matematika dari struktur diskrit. Algoritma pembangkit permutasi banyak dipakai dalam analisa graf. Komputer graf biasa diawali dengan proses penginputan edge-edge yang menentukan proses dalam komputasi graf, terutama dari sisi running time program komputer yang terkait. Banyak masalah graf yang akan lebih efisien jika graf dinyatakan sebagai permutasi siklus. Secara umum, banyaknya n permutasi dengan m siklus dapat dihitung berdasarkan metode berdasarkan rumus bilangan Striling tanpa tanda jenis pertama (Unsignless Stirling Number of The First Kind). Selain itu, menghitung enumerasi permutasi n dengan m siklus juga ditawarkan oleh Sulistyo. Dalam penelitian ini, mengenumerasikan permutasi n dengan 2 siklus dilakukan dengan cara membandingkan kedua rumusan tersebut ke dalam bentuk bahasa pemograman, yaitu Java dan melakukan uji coba dengan membandingkan dalam hal running time. Kata Kunci : Enumerasi permutasi n dengan 2 siklus, Bilangan Stirling, Rumusan Sulistyo
dinyatakan dengan formula iteratif [5]. Hal
PENDAHULUAN Algoritma
pembangkit
permutasi
tersebut melatarbelakangi penulis untuk
banyak dipakai dalam analisa graf seperti
melakukan
model optimasi berbasis graf, computer
mengenumerasikan permutasi n dengan 2
vision, berbagai masalah jaringan termasuk
siklus.
komputer dan bahkan jaringan sosial (social
perbandingan
Penelitian
ini
dalam
membandingkan
networks). Komputasi graf biasanya diawali
rumus bilangan Stiling tanpa tanda jenis
dengan proses penginputan edge-edge ini
pertama dan rumus Sulistyo dalam hal
sangat menentukan proses komputasi graf,
running
terutama dari sisi running time program
diimplementasikan kedalam bentuk bahasa
komputasi
pemograman, yaitu Java.
terkait.
Dengan
demikian
time.
Kedua
rumusan
akan
menyatakan graf sebagai permutasi dan mengembangkan algoritma yang baik untuk
LANDASAN TEORI
membangkitkan permutasi tersebut adalah
ISTILAH KOMBINATORIK
sebuah
topik
penelitian
penting
(lihat
Kombinatorik adalah ilmu yang
misalnya [6] dan [7]). Banyak masalah graf
mempelajari sifat-sifat
yang akan lebih efisien jika graf dinyatakan
struktur diskrit dimana dalam kombinatorik
sebagai permutasi siklus; salah satu masalah
struktur diskrit disebut objek kombinatorial
yang dimaksud adalah masalah jaringan.
atau objek saja. Sedangkan untuk himpunan
Selain
objek
jaringan,
masalah
lain
yang
kombinatorial
matematika dari
disebut
kelas
menggunakan pernyataan permutasi siklus
kombinatorial atau kelas saja.
adalah enumerasi graf untuk menghasilkan
Kombinatorik mempunyai 4 cabang utama
jumlah isomer senyawa kimia [2].
ilmu yaitu, pencacahan (counting) atau
Secara umum, untuk n tertentu dan bilangan
enumerasi, pembangkitan atau generasi
m yang menyatakan banyaknya siklus,
(generation), pendaftaran atau listing dan
cacahan permutasi [n] tertentu dengan m
optimasi. Pada enumerasi melakukan analisa
siklus, sering dinotasikan sebagai Cn,m, dan
matematika
dinyatakan dengan formula rekursif berikut:
cacahan struktur yang mungkin sebagai
Cn,m =
fungsi
Cn-1,m-1 +
(n-1) Cn-1,m,
yang
dari
untuk n
mendapatkan
atau
kombinatorial
jenis pertama (unsignless Stirling number of
pembangkitan membangun algoritma untuk
the
membangkitkan
kind)
[3].
Rumus
Sulistyo
mungkin.
merupakan enumerasi permutasi n dengan m siklus yang menawarkan metode baru yang
semua
S
objek
menurunkan bilangan Stirling tanpa tanda first
dalam
banyaknya
rumus
sedangkan
struktur
yang
dinyatakan sebagai π = (1) (2483) (4) (67).
DEFINISI PERMUTASI Permutasi adalah pemetaan dari
Karena siklus (8324) menyatakan dengan
suatu himpunan ke dirinya sendiri. Atau
siklus yang sama dengan (2483), maka
secara formal:
sering digunakan cara yang unik untuk menyatakan permutasi menggunakan notasi
Definisi 1: Permutasi dari himpunan S = [n]
siklus, yang disebut sebagai Notasi Siklus
= {1,2,...,n} adalah bijeksi π: S Æ S.
Kanonikal. Cara ini adalah menulis elemen
Permutasi dengan π(i) = i disebut permutasi
terbesar pada setiap siklus terlebih dahulu,
identitas.
kemudian mengurutkan setiap siklus dari kecil ke besar berdasarkan elemen-elemen
Salah representasi dari permutasi
petama pada siklus. Dengan demikian π =
adalah dengan perkalian siklusnya. Siklus
(1) (2483) (5) (67) dalam notasi siklus
dari permutasi adalah himpunan bagian dari
kanonikal π = (1) (5) (7 6) (8 3 2 4).
suatu himpunan yang elemen-elemennya masuk dalam satu orbit atau siklus dengan
MENGENUMERASIKAN PERMUTASI
panjang k dari suatu permutasi adalah urutan
N DENGAN M SIKLUS
a1, a2,...al sedemikian sehingga ai = π(ai-l)
Untuk
untuk i = 2,3, ... , l dan al = π(ak) atau
dengan
k
π (ai)= ai ([3] dan [2]). Contoh, permutasi π: 1 1
2 4
3 2
4 8
5 5
6 7
7 6
m
mengenumerasi siklus
tertentu
permutasi umumnya
digunakan rumus bilangan Stirling tanpa tanda jenis pertama (Unsignless Stirling
8 3
Number of The First Kind). Selanjutnya pada penelitian ini untuk bilangan Stirling tanpa tanda jenis pertama akan disebut
Dapat diwakili oleh diagram berikut:
rumus
bilangan
permutasi
dengan
Stirling. siklus
Enumerasi tertentu
juga
ditawarkan oleh Sulistyo [5]. Sub bab 1
2
3
4
5
6
7
berikut akan menjelaskan mengenai kedua
8
rumusan tersebut. BERDASARKAN RUMUS BILANGAN
Permutasi tersebut mempunyai 4
STIRLING
siklus (1), (2 4 8 3), (5) dan (6 7). (2 4 8 3)
Bilangan Stirling tanpa tanda jenis
adalah silkus dengan panjang l = 4, karena
pertama, dinotasikan dengan C(n,m) adalah
4
π (2) = 2. Dengan perkalian siklus, π dapat
sssbanyaknya susunan dari n objek ke dalam
m permutasi siklus yang tidak kosong.
Banyaknya simpul untuk level l pada pohon
Dimana:
pembangkit permutasi [n] dengan m siklus
C(n,0) = 0, n ≥ 1
tertentu pada Gambar 1 adalah fl .
C(n,n) = 1, n ≥ 0 C(n,1) = (n-1)!, n ≥ 0 C(n,m) = (n-1). c(n-1,m)+c(n-1.m-1), 1 < m
Gambar 1 Pohon pembangkit permutasi [n]
jenis pertama c(n,m) ([3], [2]). Rumus
dengan m siklus
bilangan
Stirling
digunakan
untuk
menunjukkan kebenaran algoritma yang
Pohon pembangkit permutasi [n]
dibangun.
dengan m siklus, yang diwakili sistem ECO (2.1) adalah pohon yang banyak simpulnya
BERDASARKAN
RUMUSAN
OLEH
pada level l = n – m sama dengan banyaknya
SULISTYO Rumus
permutasi [n] dengan m siklus, atau sama Sulistyo
dalam
[5]
dengan kardinalitas Sn,m [5].
menghasilkan rumusan enumerasi permutasi
Khusus untuk m = 2, penempatan n
dengan siklus tertentu Cn,m yang dinotasikan
pada anggota-anggota Sn,2, ditempatkan
dengan fl, untuk l = n – m,
dengan
cara
pengembangan
Johnson-
Trotter. Pembagkit permutasi dengan dua siklus Cn,2 setiap anggota (2.3) Sn-1,2 akan fl =
menghasilkan n-1. Untuk semua anggota Sn1,2
akan menghasilkan anggota Sn,2 sebanyak
(n-1)|Sn-1,2|.
Rumus diatas merupakan turunan
Banyaknya
level
dihitung
dari hasil pembangkit permutasi n dengan m
dengan menjumlahkan semua jalan dari
siklus menggunakan pohon pembangkit
simpul akar ke simpul di level l. Fungsi
sebagaimana pada gambar 2.1, level dari
pembangkit pohon permutasi [n] dengan 2
pohon
siklus
tersebut
dinyatakan
dengan
l.
Banyaknya objek permutasi n = [m + l] FΩ (x) = ∑ fl x1 = ∑ (l +1)! (1 +1/2 + .. +1/
dengan m siklus pada level l merupakan rumus
iteratif
yang
tidak
(l + 1))x1
rekursif.
Akar pada pohon dinyatakan level 0, simpul pada level 1 pada gambar 3 tertulis (1)(2)
yang
menunjukan
banyaknya
permutasi 3 dengan 2 siklus. Selanjutnya Gambar 2 Pohon Pembangkit Permutasi [4]
pada level 2 banyaknya simpul yang sejenis
dengan 2 Siklus
(B) tertulis (2)(3), sedangkan simpul yang mempunyai (2) simpul yang sejenis (T)
Untuk
menyederhanakan
pohon
mempunyai
(3)
anak
simpul
yang
pembangkit permutasi 4 dengan 2 siklus S4,2
menunjukan banyaknya permutasi 4 dengan
(gambar 2) dalam mengenumerasikan semua
2. Simpul pada level 3 yang sejenis (B)
simpul pada level tertentu, maka pada
tertulis (3)(4), sedangkan simpul yang
Sulistyo [5] objek permutasi [n] dengan 2
mempunyai dua jenis label (T) mempunyai
siklus dibagi dalam dua kelompok, yaitu
masing-masing anak sebanyak (4) yang
kelompok dimana siklus terdiri dari n saja,
menunjukan banyaknya permutasi 5 dengan
n
yaitu: (s2) = (n), ditulis sebagai πB , dan
2 siklus. Dan pada level 4 tertulis banyaknya
n
kelompok yang selain itu, ditulis sebagai πT .
simpul adalah (4)(5), sedangkan simpul
Penamaan
yang
kelompok
ini
mengikuti
penamaan east-west [8]. Pohon pembangkit
mempunyai
tiga
simpul
sejenis
mempunyai (5) anak simpul.
permutasi dengan 2 siklus yang diringkas dengan
simpul
menyatakan
banyaknya
METODE PENELITIAN
simpul pada tiap level dengan grup tertentu.
RANCANGAN APLIKASI
Gambar 3 adalah contoh ringkasan pohon
Perancangan
pembangkit permutasi 6 dengan 2 siklus.
(2)
merupakan
tahap pertama dari pembangunan suatu
(1) (1)
program
program. Tahap ini terdiri dari perancangan (2)
berdasarkan (Unified Modelling Language)
(3)
(3)
UML program dan rancangan interface.
(3)
(4)
(4)
(4)
(4)
(5)
(5)
(5)
Rancangan aplikasi permutasi dimodelkan ke dalam 3 bentuk model UML, yaitu Use Case Diagram, Class Diagram dan Activity Diagram.
Gambar 3 Ringkasan Pohon pembangkit permutasi [6] dengan 2 siklus
Sebelum program jadi pada gambar 4 menerangkan awal proses pembuatan aplikasi. PENDEFINISIAN
PERANCANGAN
KEBUTUHAN
ANTARMUKA
PENGKODEA
UJI COBA
BUG
PROGRAM JADI
Gambar 5 Diagram Use Case Aplikasi
Gambar 4 Diagram Umum Proses
Permutasi
Perancangan Aplikasi CLASS DIAGRAM Class terdiri dari
USE CASE DIAGRAM Terdapat
4
case
yaitu
utama,
metode
4, yaitu menu
formStirlingNumber,
bilangan Stirling, rumus Sulistyo, input
formSulistyoNumber dan pertolongan. Pada
banyaknya permutasi n dan m siklus dan
class
pertolongan. Actor pada aplikasi permutasi,
formSulistyoNumber menunjukan hubungan
yaitu pemakai (user) untuk use case yang
sub class yang mewarisi bagian dari class
digunakan adalah memilih perhitungan dan
utama.
memproses perhitungan berdasarkan rumus
Menu Utama
bilangan Stirling dan rumus Sulistyo. Pada rumus
bilangan
Stirling
formStirlingNumber
Pertolongan
-Stirling: boolean -Sulistyo: boolean -Tentang :boolean -Dispose()
masukkan
+tentang: boolean +Dispose()
banyaknya n permutasi dan m siklus sedangkan
rumus
Sulistyo
hanya formSulistyoNumber
memasukkan banyaknya permutasi n yang kemudian
akan
formStirlingNumber
mengenumerasikan
permutasi n dengan m siklus.
-permutasi : double int -siklus : double int
-permutasi : double int -level: double int -total: int -fac: int
-jumSiklus() -fak()
-hitungPermutasi() -fak()
Gambar 6 Diagram Class Aplikasi Permutasi
dan
ACTIVITY DIAGRAM Aktifitas dimulai pada state halaman menu utama, kemudian terjadi aktifitas pilih menu. Pada katifitas pilih menu terjadi percabangan aktifitas yaitu aktifitas pilih metode dan pertolongan. Aktifitas pilih metode terjadi percabangan yaitu metode bilangan Stirling dan metode oleh Sulistyo. Pada aktifitas metode bilangan Stirling akan menampilkan halaman bilangan Stirling.
Gambar 7 Diagram Activity Aplikasi
Sedangkan aktifitas rumus Sulistyo akan menampilkan Hamlaman
halaman metode
rumus
Sulistyo.
bilangan
Stirling
Permutasi
kemudian dilanjutkan dengan memasukkan
PSEUDOCODE
permutasi n dan m siklus yang kemudian
Pseudocode adalah kode atau tanda yang
akan dihitung berdasarkan rumus metode
menyerupai
bilangan Stirling tanpa tanda jenis pertama.
penjelasan
Halaman rumus Sulistyo terjadi aktifitas
masalah.
(pseudo) cara
atau
merupakan
menyelesaikan
suatu
memasukkan permutasi n. Sedangkan jika tidak pemakai (user) dapat kemabali ke
ALGORITMA PSEUDOCODE PADA
halaman menu utama.
RUMUS BILANGAN STIRLING
Pada
aktifitas
pertolongan
akan
1. Masukkan banyaknya n permutasi dan m
menampilkan halaman petunjuk pengguna
siklus
aplikasi dan pemakai (user) dapat kembali
2. Tentukan nilai Awal (n Å m)
ke halaman menu utama. Dan aktifitas
3. Tentukan nilai kedua (m Å 1)
keluar akan mengarah ke final state yang
4.
merupakan akhir dari alur aktifitas pada
5.
Jika n = m Æ 1, menuju kelangkah 11
aplikasi.
6.
m = 1 Æ fak (n-1), menuju
n, m Å jumSiklus
kelangkah 8 7.
Hasil (n-1) * jumSiklus (n-1,m) + jumSiklus(n-1, m-1)
8. Tentukan bilangan Faktorial (fak) 9. Jika nÅ1 || nÅ0 ; Cetak hasilnya 1
10.
Hasil Å n*fak(n-1)
Permutasi
Running Time Bilangan Striling
C2,2 C3,2 C4,2 C5,2 C6,2 C7,2 C8,2 C9,2 C10,2
15,3 miliSecond 15,6 miliSecond 15,8 miliSecond 16,4 miliSecond 16,9 miliSecond 17,4 miliSecond 17,8 mili Second 18,0 miliSecond 18,3 miliSecond
11. Selesai ALGORITMA
PSEUDOCODE
BERDASARKAN RUMUS SULISTYO 1. Masukkan banyaknya n permutasi dan m siklus 2.
lÅn–m
3.
Untuk batas perkalian kebawah ( n-1 )
4. Hitung faktorial (n-1)!
Running Time Rumus Sulistyo 14,6 miliSecond 14,0 miliSecond 14,3 miliSecond 14,7 miliSecond 15,0 miliSecond 15,3 miliSecond 14,8 miliSecond 15,6 miliSecond 15,4 miliSecond
Berdasarkan tabel 1 data running
5. Total = faktor
time dihasilkan ketika main dieksekusi.
6. Untuk i = 1, 2, ..., l
Dengan Profiling waktu yang dihasilkan
7.
Faktor Å (Faktor/ (i1 + 1)) * i
dalam bentuk tabel. Pada masing-masing
8. Total = total + faktor
rumus antara bilangan Stirling tanpa tanda jenis
ANALISA PROGRAM
pertama
menunjukan
dengan
rumus
perbedaan
Sulistyo
waktu.
Pada
dengan
bilangan Stirling membutuhkan waktu lebih
membandingkan running time pada masing-
lama dalam mengeksekusi dibandingkan
masing main dengan menggunakan Profiling
dengan rumus Sulistyo. Ini dikarena pada
Point. Data perbandingan yang digunakan
perbedaan kedua proses memiliki algoritma
adalah permutasi C2,2, C3,2, C4,2, C5,2, C6,2,
yang
C7,2, C8,2, C9,2, C10,2. Running time dimulai
menggunakan algoritma rekursif sedangkan
ketika munculnya form metode yang dipilih.
rumus Sulistyo menggunakan algoritma
Hasil perbandingkan akan dihasilkan dengan
iteratif.
Perbandingan
dilakukan
berbeda,
pada
bilangan
Stirling
running time dan kapasitas alokasi memori.
KESIMPULAN DAN SARAN Tabel 1 Perbandingam Running Time
KESIMPULAN
Berdasarkan Bilangan Stirling dengan
Hasil running time dengan menggunakan
Rumus Sulistyo
Profiling Point menunjukan bahwa rumus bilangan Stirling yang diformulasikan dalam bentuk algoritma rekursif mencatat waktu lebih lama dibanding rumus Sulistyo secara iteratif. Hal ini dikarenakan pada rekursif membutuhkan proses pemanggilan dalam
menghasilkan
output.
Sedangkan
pada
iteratif hanya membutuhkan satu proses dengan
melakukan
menerus
higga
terpenuhi.
perulangan
batas
Namun
yang bilangan
[6]
terus
ditentukan Stirling
memiliki kapasitas yang lebih kecil yaitu
[7]
888 Byte sedangkan rumus Sulistyo yaitu 1024 Byte. [8]
SARAN Terbatasnya aplikasi ini diharapkan agar mengenumerasikan permutasi dapat berlaku pula rumus umum berdasarkan rumusan Sulisto yaitu, Cn,m kedalam bentuk bahasa pemograman.
DAFTAR PUSTAKA [1]
[2]
[3]
[4]
[5]
Bernini A, E. Grazinni, E. Pergola, R. Pinzani, 2007. A General Exhaustive Generation Algorithm for Gray Structures, Journal Acta Informatica, Vol. 44, no. 5, pp. 361376 Babic D, D.J. Klein, J. Von Knop, N. Trinajstic, 2004. Combinatorial Enumeration in Chemistry, Chemical modelling : Applications and Theory, Royal Society of Chemistry, vol. 3, pp. 126-159 Bona M., 2002. A walk through Combinatorics. An Introduction to Enumeration and Graph Theory. New Jersey, World Scientific Publishing Ruskey F., 2003. Combinatorial Generation. http://www.1stworks.com/ref/Ruske yCombGen.pdf, 19 Agustus 2007 Sulistyo Puspitodjati., 2010. Algoritma Pembangkit Lengkap
Permutasi Siklus Tertentu dengan Banyaknya Elemen Sebagai Peubah. Sedgewick R., 2007. Permutation Generation Methods, Dagstuhl Workshop on Data Stuctures,Wadem, Germany. http://www.cs.princeton.edu/~rs/talk s/perms.pdf, 18 Juli 2008 Sedgewick R., 2007. Finding Paths In Graphs, Adobe System India. http://www.cs.princeton.edu/~rs/talk s/PathsInGraphs07.pdf, 3 September 2007 Wilf H. S., 1999. East Side, West side... an introduction to combinatorial families-with Maple programming. http://www.math.upenn.edu/~wilf/ea stwest.pdf, 5 juli 2008
