Algoritma Pembangkitan Lengkap Permutasi dengan Siklus Tetap dan Banyaknya Elemen Sebagai Peubah
Sulistyo Puspitodjati, Asep Juarna, Ernastuti
Djati Kerami
Jurusan Teknik Informatika Universitas Indonesia
Jurusan Matematika FMIPA Universitas Indonesia
Depok, Indonesia
Depok, Indonesia
e-mail korespondensi:
[email protected] Ringkasan Pembangkitan lengkap (exhaustive generation) adalah salah satu cabang utama kombinatorik. Topik makalah ini adalah pembangkitan lengkap permutasi siklus menggunakan metoda pohon pembangkit (generating tree), dan karena aturan pengembangannya ke simpul-simpul selanjutnya menggunakan aturan suksesi (succession rule) maka pembangkitan juga dalam metode ECO (enumerating combinatorial object). Dua penelitian terdahulu tentang topik yang sama dilakukan masing-masing oleh Baril (2006) dan Poneti (2008). Penelitian Baril menghasil-kan daftar kode Gray (Gray code list) permutasi siklus. Poneti membangkitkan π n,m dari π n,m−1 secara rekursif, dengan kata lain permutasi siklus Poneti dibangkitkan menurut jumlah siklusnya pada himpunan [n] tetap. Penelitian ini merupakan sudut pan-dang lain dari penelitian Poneti, yaitu permutasi siklus dibang-kitkan menurut himpunannya pada jumlah siklus tetap, atau π n,m dibangkitkan dari π n−1,m . Hasilnya adalah sebuah algoritma pem-bangkitan permutasi siklus berbasis metoda ECO yang bersifat non rekursif dengan kompleksitas CAT (constant amortized time) karena obyek-obyek π n,m dibangkitkan dari sebuah π n−1,m hanya melalui satu operasi penyisipan. Keywords-permutasi siklus; pembangkitan lengkap; pohon pembangkit; metode ECO; algoritma pembangkitan; CAT.
1 Pendahuluan Kombinatorik adalah ilmu yang mempelajari sifatsifat matematik dari struktur diskrit; dalam kombinatorik struktur diskrit disebut obyek kombinatorial atau obyek saja, sedangkan himpunan obyek kombinatorial disebut kelas kombinatorial atau kelas saja.
Kombinatorik mempunyai empat cabang utama ilmu atau penelitian: pencacahan (counting) atau enumerasi (enumeration), pembangkitan atau generasi (generation), pendaftaran atau listing, dan optimalisasi. pembangkitan membangun algoritma untuk membangkitkan semua struktur yang mungkin. Ada dua jenis pembangkitan yaitu pembangkitan
lengkap (exhaustive generation) dan pembangkitan acak (random generation). Pembangkitan lengkap membangkitkan semua obyek tanpa ada obyek yang tercacah ganda (no repetition) dan tanpa ada obyek yang tidak tercacah (no omission). Pembangkitan acak membangkitkan contoh (sample) obyek yang secara statistik bisa mewakili semua obyek dari kelas yang diberikan. Pembangkitan acak biasanya dilakukan jika pembangkitan lengkap tidak mungkin dilakukan atau tidak praktis untuk dilakukan terutama karena anggota kelas yang sedang diamati sangat besar [5]. Salah satu teknik enumerasi dan juga pembangkitan lengkap obyek kombinatorial yang populer saat ini adalah teknik enumerasi dan pembangkitan menggunakan pohon pembangkit (generating tree). Pohon pembangkit adalah sebuah pohon dalam konteks teori graf di mana simpul-simpulnya menyatakan obyek (untuk tujuan pembangkitan) atau angka yang menunjukkan banyaknya simpul anak (untuk tujuan enumerasi). Belakangan, untuk tujuan enumerasi, pohon pembangkit dilengkapi dengan sebuah aturan rekursif yang tepat mewakili pohon tersebut [12] yang melahirkan metoda ECO (enumerating combinatorial objects)[3]; aturan rekursif dimaksud disebut aturan suksesi (succession rule). Dengan metode ECO, setiap obyek diekspansi dari obyek yang lebih pendek dengan menerapkan aturan suksesi (succession rule). Analisa matematis selanjutnya mentransformasikan formula aturan suksesi ke sebuah persamaan hubungan rekursif (recurrence relation). pohon pembangkit mempunyai pemanfaatan yang penting dalam kombinatorial, yaitu bijeksi dan pembangkitan acak[10]. Topik makalah ini adalah enumerasi dan pembangkitan kelas kombinatorial permutasi, khususnya permutasi dalam pernyataannya sebagai produk siklus (product of cycles permutation) atau sering disingkat sebagai ‘permutasi siklus’ atau ‘siklus’ saja. Algoritma pembangkitan permutasi banyak dipakai dalam analisa graf seperti model optimalisasi berbasis graf, computer vision, berbagai masalah jaringan termasuk komputer dan bahkan jaringan sosial (social networks). Hasil utama penelitian yang disajikan dalam disertasi ini adalah algoritma pengembangan lengkap
permutasi dengan siklus menggunakan metoda pohon pembangkit.
2 Definisi dan Istilah 2.1
Permutasi
Permutasi adalah pemetaan dari suatu himpunan bilangan asli ke dirinya sendiri, atau secara formal dapat didefinisikan sebagai berikut: Definisi 1: Permutasi dari himpunan S = [n] = 1, 2, ..., n adalah fungsi bijeksi π : S S. Permutasi π(i) = i disebut permutasi identitas. Permutasi dapat direpresentasikan dengan menjajarkan semua nilai π(i), untuk i = 1, . . . , n dalam satu baris. Contoh salah satu permutasi π dari [7] dalam notasi satu baris ditulis sebagai untai : 2 4 3 1 657 Salah representasi dari permutasi adalah dengan perkalian siklusnya. Siklus dari permutasi adalah himpunan bagian dari suatu himpunan yang elemenelemennya masuk dalam satu orbit. Atau siklus dengan panjang k dari suatu permutasi adalah urutan a1 , a2 , . . . , al sedemikian sehingga ai = π(ai−1 ) untuk i = 2, 3, . . . , l, dan a1 = π(al ) atau π l (ai ) = ai . ([Rus03] dan [Bón02]). Contoh, permutasi π berikut: 1 4 2 8 5 7 6 3. Permutasi tersebut mempuyai 4 siklus (1), (2 4 8 3), (5), and (6 7). (2 4 8 3) adalah siklus dengan panjang l = 4, karena π 4 (2) = 2. Dalam perkalian siklus, π dapat dinyatakan sebagai π = (1)(2483)(5)(67). Karena siklus (8324) menyatakan siklus yang sama dengan (2483), maka sering digunakan cara yang unik untuk menyatakan permutasi menggunakan notasi siklus, yang disebut sebagai notasi siklus kanonikal. Cara ini adalah menulis elemen terbesar pada setiap siklus terlebih dahulu, kemudian mengurutkan setiap siklus dari kecil ke besar berdasarkan elemenelemen pertama pada siklus. Dengan demikian π = (1)(2483)(5)(67) dalam notasi siklus kanonikal adalah π = (1)(5)(76)(8324). Banyaknya permutasi [n] dengan m siklus adalah bilangan Stirling tanpa tanda jenis pertama c(n,m) ([11, 18]). Dimana
Operator ECO c(n, n) = 1, c(n, 1) = (n − 1)! c(n, m) = (n − 1).c(n − 1, m) + c(n − 1, m − 1), 1 < m < n. (1)
Makalah ini akan membahas permutasi dengan m siklus. Rumus stirling digunakan untuk menunjukkan kebenaran algoritma yang dibangun
2.2
Misalkan O adalah kelas objek kombinatorial dan p: O N adalah parameter yang hingga pada O, yaitu parameter p sedemikian sehingga On = O ∈ O : p(O) = n dari objek berukuran n adalah hingga. Misalkan v : O 2O adalah operator yang sedemikian sehingga v(On ) ⊆ 2O n+1 . Operator v menggambarkan bagaimana objek kecil menghasilkan objek yang lebih besar.
Pembangkitan Objek kombinatorial Proposisi 2-1: Jika v memenuhi, untuk setiap n ≥ 0, dan Pohon Pembangkit.
Salah satu bidang dalam kombinatorik adalah pembangkitan objek secara lengkap. Pembangkitan ini berarti membangkitkan (menghadirkan) semua anggota dari kelas kombinatorial tertentu secara efisien yang sedemikian sehingga setiap anggota muncul tepat sekali. Salah satu pendekatan untuk pembangkitan lengkap adalah dengan yang disebut pohon pembangkit. Pohon pembangkit adalah pohon yang menggambarkan keluarga tertentu dari objek kombinatorial; tiap simpul berhubungan dengan satu objek, dan cabangnya menuju simpul yang mengkodekan alternatif yang dipilih dalam mengkonstruksikan objek. Pohon pembangkit menjanjikan komputasi yang cepat dalam mengenumerasi barisan objek. Metode pohon pembangkit ini disistematisasikan oleh Barcucci, Del lungo, Pergola, and Pinzani, dengan nama sistem ECO (enumerating combinatorial objects) [3]. Dalam metode ECO ini setiap objek diperoleh dari objek yang lebih kecil dengan melakukan ekspansi lokal. Seringkali ekspansi lokal tersebut sangat teratur dan dapat dijelaskan dalam aturan suksesi. Metode ECO ini telah ditunjukkan efektif untuk beberapa struktur kombinatorik, seperti: objek Catalan dalam [5] dan [12], untuk permutasi penghindaran pola umum (generelazid pattern avoidance) dalam [23], convex polyominoespan dalam [17], dan untuk struktur Gray dalam [4]. Namun penelitian-penelitian tersebut belum membahas pembangkitan permutasi siklus dengan pohon pembangkit atau metode ECO tersebut. Bagaimana metode ECO bekerja dijelaskan dalam [5],[10], dan [3], sebagaimana berikut.
1. untuk setiap O’ ∈ On+1 , akan terdapat O ∈ On sedemikian sehingga O’ ∈ v, dan 2. untuk setiap O, O’ ∈ On , akan menggambarkan v(O) ∩ v(O’) = ∅ kapanpun O 6= O’, maka famili himpunan Fn+1 = v(O): O ∈ On adalah partisi dari On+1 . Operator v yang memenuhi kondisi 1 dan 2 tersebut di atas, dikatakan sebagai operator ECO. Jadi operator ECO membangkitkan semua objek O sedemikian sehingga setiap objek O’ ∈ On+1 diperoleh secara unik dari O ∈ On . Operator ECO yang sedang melakukan ekspansi lokal pada objek yag disebut situs aktif dari objek. Operator ECO dapat digambarkan dengan pohon pembangkit, yaitu: pohon berakar yang simpu-simpulnya berhubungan dengan objek O. Akar yang ditempatkan pada level 0 pada pohon, adalah objek dengan ukuran terkecil, m. Objek-objek dengan ukuran sama berada pada level yang sama dan anak dari objek O, adalah yang dihasilkan dari O melalui v. Jika |On |n adalah urutan yang ditentukan oleh banyaknya objek berukuran n, maka maka f O(x) = Σn ≥ m|On|xn adalah fungsi pembangkitnya. Aturan Suksesinya Aturan suksesi Ω adalah sistem ((a), P), mengandung aksioma (a) dan himpunan produksi atau aturan penulisan P didefinisikan pada himpunan label M ⊂ N+:
2.3
Dekomposisi Standar dan Permutasi Pengembangan dengan cara Baril ini, merupakan sifat utama yang dipegang oleh penulis dalam dengan Siklus
Poneti dan Vajnovszki[20]menunjukkan bahwa untuk sembarang π ∈ Sn dapat ditulis secara unik dalam dekom-posisi standar sebagai dengan cara memilih pi = π −1 (i), kemudian mengganti π dengan π [22c5] <π −1 (i),i >, untuk i bergerak dari n ke 1. Dari permutasi π ∈ Sn dalam dekomposisi standar, dapat ditentukan D(π) = maxi π(i) 6= i yang juga merupakan maxi pi 6= i. Berdasarkan sifat D ini maka Poneti dan Vajnovszki[20] membangun algoritma pembangkitan permutasi π ∈ Sn,m , yaitu π ∈ Sn dengan m siklus, sebagai berikut:
mengembangkan pohon pembangkit, yang akan disajikan pada makalah ini.
3 Pohon Pembangkit Untuk Permutasi Dengan Siklus
Mengikuti pola pengembangan permutasi [n] dengan satu siklus [9], maupun 2 siklus[25] dan pembentukan semua permutasi n dengan m siklus, Sn,m , menurut [5], maka pengembangan digeneralisasi dengan membangun definisi fungsi i π n berikut. Pendefinisian fungsi ini adalah formalisasi dari proses penyisipan n atau n+1 pada semua kemungkinan pon Y π = < pi , 1 >=< p1 , 1 > . < p2 , 2 > .... < pn , n > dengan pi ∈ [1, i] sisi pada permutasi [n], saat menghasilkan permui=1 tasi [n+1] dengan satu maupun 2 siklus. Definisi 2: Fungsi i π n adalah pemetaan pada: 1. Tentukan D(π) < n Sn,m × [n] Sn+1,m , 1 ≤ m ≤ n, i ∈ [n], yang 2. Untuk setiap j , D(π) < j ≤ n, dan untuk setiap memetakan sembarang permutasi π n ∈ Sn,m menjadi l, 1 ≤ l < j, tentukan permutasi π’ = π.
, π’ permutasi i π n+1 ∈ Sn+1,m ∈ Sn,m−1 πn (i) untuk j = n + 1 i n + 1 untuk j = i π (j) = (n+1) Algoritma ini tidak membangun permutasi Sn,m dari π (j) untuk yang lain n Sn−1,m melainkan dari Sn,m−1 . Berbeda dengan pembangkitan yang akan disajikan dalam makalah, Fungsi i π n pada Definisi 2 jelas adalah fungsi satudimana pembangkitan permutasi yang akan dissatu. Pembangkitan semua permutasi anggota Sn,m ajikan adalah pembangkitan permutasi Sn,m dari lainnya, selain dengan mengimplementasi i π n , maka Sn−1,m . berturut-turut m diganti m-1, dan n bertindak sebagai n-1, sementara, i π n (n) = n. Hal ini untuk 2.4 Pembangkitan Permutasi dengan memenuhi kemungkinan bahwa permutasi [n] mempunyai siklus-siklus panjang satu. Untuk memenuhi Siklus oleh Baril keanggotaan Sn,m , yang siklus ke-m adalah (n), Baril dalam[16]menunjukkan pembentukan Sn,m , maka harus dibangun semua kemungknan permutasi yaitu permutasi [n] dengan m siklus dari Sn−1,m dan [n-1] dengan m-1 siklus. Selanjutnya jika siklus sm−1 Sn−1,m−1 . Pembentukan dilakukan dalam dua cara: = (n-1) dan siklus ke-m sm = (n), maka harus dibangun semua kemungkinan siklus-siklus sj , j = 1, 2, 1. jika π ∈ Sn−1,m , n ≥ 2, 1 ≤ m < n, maka dapat . . . , m-2 atau dengan kata lain membangun semua diperoleh π’ ∈ Sn,m , dengan memetakan π’(i) = kemungkinan permutasi Sn−2,m−2 dengan menerapkan i π n−2 . Demikian seterusnya sampai diperoleh n dan π’(n) = π(i), 1 ≤ i ≤ n. semua permutasi Sn,m . 2. jika π ∈ Sn−1,m−1 , n ≥ m ≥ 2, maka dapat diperPermutasi dengan siklus dalam penelitian ini dioleh π” ∈ Sn,m , dengan menambahkan n pada tulis dalam bentuk π n = (s1 ). . . (sm ), si adalah sikposisi n. lus ke-i dan tidak ditulis dalam bentuk kanonik,
akan tetapi pada tiap siklus elemen terkecilnya ditulis pada elemen pertama siklus. Siklus-siklus diurut berdasarkan urutan elemen pertama tersebut dari kecil ke besar. si adalah siklus ke-i. Pengembangan dimulai dengan permutasi identitas (1)(2). . . (m), untuk siklus m yang diinginkan. Selanjutnya, pembangkitan dilakukan dengan mengembangkan Sn+1,m . Permutasi anggota Sn+1,m dihasilkan dari mengimplementasikan fungsi i π n+1 , untuk i ∈ [n]. Setelah itu, membangun objek-objek permutasi anggota Sn+1,m yang lain dengan pertama meletakkan elemen n+1 pada siklus ke-m, yaitu sm = (n+1). Kemudian mengganti nilai n+1 dengan n dan mengaplikasikan fungsi i π n , i ∈ [n-1]. Proses pembang-kitan dilanjutkan dengan meletakkan sm−1 = (n), dan tetap meletakkan siklus sm = (n+1), kemudian mengimplementasi fungsi i π n−1 . Proses diteruskan sampai sampai i π 2 terimplemen-tasikan dalam rangka melengkapi Sn−1,m . Teorema 4.4: Dengan menerapkan fungsi i π pada definisi 4.1, maka akan terbentuk semua anggota Sn,m secara rekursif dari Sn−1,m dan Sn−1,m−1 . Dengan demikian banyaknya anggota Sn,m memenuhi bilangan Stirling jenis pertama tanpa tanda cn,m = (n-1)cn−1,m + cn−1,m−1 Bukti: Dari definisi fungsi maka terbentuk (n-1) kali kardinalitas |Sn−1,m | dan selebihnya anggota Sn,m yang lain dibentuk dari pengembangan Sn−1,m−1 . Sehingga banyaknya Sn,m adalah (n1) |Sn−1,m | + |Sn−1,m−1 | atau memenuhi bilangan Stirling jenis pertama tanpa tanda cn,m , yaitu cn,m = (n-1)cn−1,m + cn−1,m−1 Untuk memudahkan pengembangan, maka permutasi dinyatakan dalam notasi siklus, sehingga jumlah siklus yang tetap terpelihara. Kemudian implementasi fungsi i π n+1 , untuk i ∈ [n], diintrepetasikan dengan meletakkan atau menyisipkan elemen n+1 kedalam siklus sk = (sk1 , sk2 , . . . ) secara berturut-turut ke posisi j = 2, . . . , |sk |, dengan |sk | adalah panjang siklus untuk semua siklus k. Pembangkitan dalam penelitian ini dilakukan untuk sembarang permutasi [n] dengan m siklus. Pohon pembangkit diawali dengan permutasi identitas Sm,m pada simpul akar, dan akar dari pohon ini dikatakan sebagai level 0. Selanjutnya, simpul akar ini akan mempunyai anak yang dimulai
dengan membangun permutasi anggota Sn+1,m hasil mengimplemen-tasikan fungsi i π n+1 , untuk i ∈ [n], yaitu menyisipkan elmenen n+1= m+1 ke dalam m-siklus dalam permutasi identitas, berturut-turut di posisi i ∈ [n]. Simpul-simpul untuk objek hasil dari pembangkitan ini diberi label on+1 , dan simpul dengan label ini akan sebanyak n. Algoritma pembangkitan permutasi anggota Sn,m dapat dilihat pada Algoritma 1. Algoritma ini merupakan generalisasi dari Sn,m . Algoritma 1 : 1. Input n dan siklus m yang diinginkan 2. t = n - m 3. Simpul akar 1 o1 = (1)(2)...(m). 4. Untuk level l = 1, ..., t 5. Untuk j = l, ..., m+ l 6. Untuk i = 1, ..., j 7. Untuk k = 2, . . . , |sik | 8. Buat simpul anak k oj+1 dengan menyi-sipkan elemen j+1 ke-siklus sik pada posisi k 9. Jika j <> m+ l 10. sm (m+ l) 11. Selesai Berdasarkan pembangkitan pada Algoritma 1, konstruksi dimulai dengan akar o1 , Sn,m dibangun dengan membentuk himpunan-himpunan oj . Setiap simpul aktif oj mempunyai j anak oj+1 , j-1 anak oj , dan seterusnya sampai m+l-1 anak om+l . Pohon terus berkembang sampai objek om+l dengan n=m + l tercapai. Sehingga aturan suksesi untuk sistem ECO permutasi [n] dengan siklus m pada penelitian ini adalah sistem yang dimulai dengan aksioma permutasi identitas π m = (1)(2). . . (m), dan selanjutnya mengikuti aturan berikut: O1, permutasi identitas Ω= Oj (Oj+1 )j (Oj+1 )j+1 ...(Om+1 )m + l − 1 (2)
f1 =
l
mP +l−1 i1 i2 = i1 + 1
mP +l−1 i2 i2 = i1 + 1
Secara umum pohon dapat digambarkan sebagaimana pada Gambar 1. Simpul pada pohon Gambar 1 dengan label joj−1 adalah bentuk ringkas dari pohon dengan simpul oj−1 yang sebanyak j. Sehingga level-1 dari pohon pembangkit ini akan mempunyai simpul sebanyak (m + m-1 + . . . + 1). Pada level-2, j-1 objek oj , masing-masing akan mempunyai j anak oj+1 , j+1 anak oj+2 , sampai m+l-1 anak om+l . Dengan demikian berdasarkan pohon pembangkit ini, dapat dienumerasi banyak permutasi n dengan siklus m tertentu dengan mengitung banyaknya simpul pada level l dimana n = m+l. Secara umum banyaknya permutasi [n] dengan siklus m tertentu berdasarkan pohon pembangkit adalah sebagaimana pada rumus (3). Banyaknya simpul untuk level-l pada pohon pembangkit permutasi [n] dengan m siklus tertentu pada Gambar 1 adalah fl dengan sebagai persamaan 3:
Algoritma pembangkitan pohon permutasi [n] dengan m siklus pada Algoritma 1, menghasilkan simpul-simpul yang mewakili semua objek anggota Sn,m , dengan cara menyisipkan elemen di setiap siklus di setiap level untuk maing-masing objek oj . Dengan demikian pada setiap level, algoritma melakukan penyisipan sebanyak fl kali untuk fl pada rumus 3. Jika penyisipan dihitung 1 waktu komputasi, maka algoritma melakukan dalam O(c(n,m)) waktu dengan n tercapai setelah mencapai level l = n – m. Algoritma menghasilkan satu objek dengan satu operasi yaitu penyisipan, dan pada level l yang menunjukkan n = m + l, algoritma menghasilkan objek sebanyak c(n,m). Dengan demikian jumlah total komputasi dibagi banyaknya objek yang terbentuk terbatasi oleh konstanta. Hal ini menunjukkan Algoritma 1 adalah algoritma yang CAT (Constant Amortized Time) yang merupakan syarat algoritma pembangkitan objek kombinatorial yang efektif.
4 Penutup Pembangkitan lengkap permutasi [n] dengan m siklus (dinotasikan π n,m ) berhasil dilakukan dengan
P
......
,l = 0 m +Pl − 1
l = 1, 2
(3)
i1 = i1−1 + 1 menggunakan metoda ECO (enumerating combinatorial object). Algoritma pembangkitan disusun dengan terlebih dahulu didefinisikan pemetaan satusatu yang memetakan π n−1,m ke π n,m . Pendefinisian dilakukan untuk memastikan tidak terjadi pembangkitan ganda ataupun pembangkitan yang terlewatkan. Algoritma yang dihasilkan bersifat non rekursif dengan kompleksitas CAT (constant amortized time) karena obyek-obyek π n,m dibangkitkan dari sebuah π n−1,m hanya melalui satu operasi penyisipan. Pola pembangkitan pada algoritma tersebut, yang jelas terlihat pada pohon pembangkit (generating tree) menunjukkan adanya pola cacahan bilangan Stirling jenis pertama tanpa tanda (signless Stirling number of the first kind). Fakta ini memastikan tidak terjadi pembang-kitan ganda ataupun pembangkitan yang terlewatkan. Algoritma yang dihasilkan pada penelitian ini diharapkan dapat menjadi pijakan untuk penelitian lanjutan tentang permutasi siklus, salah satunya adalah penentuan daftar kode Gray untuk permutasi siklus
References [1] Bogomolny A. Various ways to define a permutation from Interactive Mathematics Miscellany and Puzzles. New Jersey, World Scientific Publishing, 2008. [2] J. Von Knop N. Trinajstic Babic D, D.J. Klein. Combinatorial enumeration in chemistry. In Chemical Modelling : Applications and Theory, Royal Society of Chemistry, volume 3, pages 126 – 159, 2004. [3]  A. Denise  P. Flajolet  D. Gardy D. GouyouBeauchamps Banderier C.,  M. Bousquetc Mà lou. Generating functions for generating trees. In Discrete Mathematics, volume 246(13)„ pages 29–55, 2002.
[4] E Grazzini Bernini A., I Fanti. An exhaustive generation algorithm for catalan objects and others. In PU.M.A., volume 17, pages 39–53, 2006.
[14] West J. Generating trees and forbidden subsequences. In Proceedings of the 6th conference on Formal power series and algebraic combinatorics, pages 363 – 374, 199.
[5] E. Pergola R. Pinzani Bernini A, E. Grazzini. [15] Asep Juarna. Combinatorial Isomorphism AnalA general exhaustive generation algorithm for ysis On Some Extensions Of A Simion-Schmidt’s Bijection. Dissertation in Informatics, LE2I – gray structures. In Journal Acta Informatica, U.F.R des Science des Technique, Universite de volume 44„ pages 361–376, 2007. Bourgogne. [6] Savage C. A survey of combinatorial gray codes, siam review. volume 39, pages 605 – [16] Baril J. L. Gray code for permutation with a fixed number of cycle. In Discrete Mathematics, 629, 1997. volume 307, pages 1559–1571, 2006. [7] Wilson M. C. Random and exhaustive generation of permutations and cycles. In Journal [17] A. Frosini S. Rinaldi Lungo D. A., E. Duchi. Enumeration of convex polyominoes using the eco Annals of Combinatorics,, volume 12, of 509 method, discrete mathemathics and theoretical 520, 2007. computer science ab(dmcs). pages 103–116, [8] R.L. Rivest Cormen T.H., C.E. Leiserson. Intro2003. duction to Algorithm. McGraw Hill Book Com[18] Bona M. A walk through combinatorics. an inpany, New York, 1990. troduction to enumeration and graph theory. [9] Sulistyo P. dan Djati Kerami. Pembangkitan 2002. permutasi dengan siklus. In Prosiding Konferensi Nasional Matematika XIV. Palembang, [19] Adnan M.A. Effcient enumeration of combinatorial objects. Master’s thesis, B.Sc. Engg. Thepages 275 – 280, 2008. sis, Department of Computer Science and Engi[10] Duchi E. ECO method and Object Grammars: neering Bangladesh University of Engineering two methods for the enumeration of combinaand Technology (BUET) Dhaka. torial objects. Tesi dell’ Universita degli Studi di Firenze, Dottorato di Ricerca in Ingegne- [20] V. Vajnovszki Poneti M. Generating restricted classes of involutions, bell and stirling permuria Informatica e dell’Automazione, XV Citations. In European Journal of Combinatoric, clo, Universit_a Degli Studi di Firenze, http:// volume 31, pages 553–564, 2010. www.dsi.unifi.it / DRIIA / RaccoltaTesi/ Duchi, 2003. [21] Sedgewick R. Permutation generation methods, dagstuhl workshop on data structures. Wadern, [11] Ruskey F. Combinatorial generation. 2003. Germany., 2002. [12] R. Pinzani Ferrari L. Catalan like numbers and succession rules, pure mathematics and appli- [22] Sedgewick R. Finding paths in graphs, adobe systems india. 2007. cations. volume 16, pages 229–250., 2005. [13] Irving J. Minimal transitive factorizations of permutations into cycles, canadian journal of mathematics. volume 61, pages 1092–111, 2009.
[23] Elizalde S. Generating tree for permutations avoiding generalized patterns,. In Journal Annals of Combinatorics, volume 11„ pages 435– 458, 2008.
[24] Wilf H. S. East side, west side an introduction to combinatorial families-with maple programming. 1999. [25] Djati Kerami Ernastuti Sulistyo P, Asep Juarna. Pembangkit permutasi dengan dua siklus, akan diterbitkan prosiding seminar nasional matematika,. Universitas Indonesia, Depok, 2010. [26] Vajnovzki V. Generating combinatorial objects by eco method the lyndon words case, lecture notes, gunadarma university, jakarta. 2006.
