Algoritma Pembangkitan Lengkap Permutasi dengan Siklus Tetap dan Banyaknya Elemen Sebagai Peubah

Abstract

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.