Dalam matematika, sebuah struktur/objek matematika pada umumnya dapat direpresentasikan dalam berbagai bentuk. Contohnya, fungsi dapat direpresentasikan dalam bentuk formula, tabel, diagram, ataupun grafik. Demikian pula halnya dengan himpunan, yang dapat direpresentasikan dalam bentuk eksplisit (menuliskan semua elemennya, misalnya: {a,b,c,d}), dalam bentuk generator (hanya menuliskan kriterianya saja; misalnya: {x|x bilangan genap}), ataupun dalam bentuk diagram Venn.
Sebuah himpunan dengan n elemen memiliki 2n subhimpunan. Sebagai contoh, himpunan {a,b,c} memiliki subhimpunan sebagai berikut:
- Subhimpunan tanpa anggota: {}.
- Subhimpunan dengan 1 elemen: {a}, {b}, dan {c}.
- Subhimpunan dengan 2 elemen: {a,b}, {a,c}, dan {b,c}.
- Subhimpunan dengan 3 elemen: {a,b,c}
Jadi, himpunan {a,b,c} (dengan n = 3) memiliki 23 = 8 subhimpunan.
Cukup mudah, ya? Namun, untuk n yang lebih besar tentu menjadi hal yang tidak mudah. Kita tahu bahwa untuk n = 7 (misalnya himpunan {a,b,c,d,e,f,g}) terdapat 27 = 128 subhimpunan. Pertanyaannya, bagaimana sistematika untuk menuliskan ke-128 subhimpunan tersebut secara lengkap, tanpa ada satupun subhimpunan yang terlewati, dan tanpa ada yang berulang? Hmm, terdengar seperti pertanyaan iseng. Namun kenyataannya ini bukanlah pertanyaan iseng, karena pertanyaan ini termasuk dalam kajian exhaustive generation of objects yang ada dalam domain kombinatorik dan banyak digunakan untuk mencari solusi optimal dari suatu permasalahan.
Untuk menjawab pertanyaan tersebut, mari kita gunakan bantuan objek lain yang dicacah/dihitung dengan cara serupa. Objek itu adalah untai biner, yaitu sebuah barisan yang terdiri dari 0 dan 1. Contoh untai biner adalah 101, 001011, 10010110, dan sebagainya. Terdapat 2n kemungkinan untuk untai biner dengan panjang n. Misalnya untuk n = 3, diperoleh 23=8 kemungkinan untai biner, yaitu 000, 001, 010, 011, 100, 101, 110, dan 111. Nah, karena banyaknya untai biner dan banyaknya subhimpunan sama-sama dicacah dengan 2n, kita dapat membuat sebuah korespondensi satu-satu antara mereka. Dengan kata lain, sebuah untai biner merepresentasikan tepat sebuah subhimpunan.
Terlebih dahulu kita tetapkan urutan elemen-elemen himpunan. Urutan bisa secara alfabetis/leksikografis, ataupun yang lainnya. Misalkan himpunan {a,g,e,i,h}, dapat diurutkan menjadi {a,e,g,h,i}; {3,7,2,5} dapat diurutkan menjadi {2,3,5,7}. Setelah itu, buatlah daftar seluruh untai biner dengan panjang n (dengan n adalah banyaknya anggota himpunan). Untuk mudahnya, daftar untai biner tersebut dapat diurutkan secara naik (ascending order) atau turun (descending order).
Kemudian, konversikanlah setiap untai biner tersebut menjadi sebuah subhimpunan, dengan aturan: jika digit ke-i pada untai biner adalah 1, maka elemen urutan ke-i pada himpunan ada dalam subhimpunan. Sebaliknya, jika digit ke-i pada untai biner adalah 0, maka elemen urutan ke-i pada himpunan tidak ada dalam subhimpunan. Misalkan himpunan dengan 4 elemen {a,b,c,d}, maka 1101 merepresentasikan {a,b,d}, 0000 merepresentasikan {}, 1010 merepresentasikan {a,c}, dan seterusnya. Lebih lengkapnya, penerapan metode ini untuk menuliskan semua subhimpunan dari {a,b,c,d} dijelaskan dalam tabel.
Variasi urutan dengan minimal change order
Urutan untai biner dapat diatur kembali sedemikian sehingga setiap dua untai biner yang berurutan hanya berbeda satu digit saja. Urutan seperti ini disebut urutan perubahan minimal (minimal change order), atau istilah lainnya adalah kode Gray. Implikasi dari diterapkannya pengurutan seperti ini adalah: subhimpunan berikutnya diperoleh dengan menambah atau menghilangkan sebuah elemen dari subhimpunan sebelumnya. Oleh karena itu, minimal change order memberikan prosedur yang lebih efisien dibanding pengurutan lainnya.
Perhatikan tabel yang menampilkan semua untai biner diurut berdasarkan minimal change order. Dapat dilihat bahwa dua subhimpunan yang berurutan hanya berbeda dengan penambahan atau penghilangan satu elemen saja.
Dengan memanfaatkan korespondensi satu-satu antara untai biner dengan subhimpunan, pekerjaan untuk menuliskan semua subhimpunan dari sebuah himpunan menjadi lebih mudah dan sistematis. Tak kalah pentingnya, teknik ini menjamin dihasilkannya semua subhimpunan yang dapat dibentuk, tepat satu kali (tanpa ada perulangan), dan tanpa ada yang terlewatkan.
Bahan bacaan:
Penulis:
Ahmad Sabri, alumnus Universitas Indonesia dan Université de Bourgogne, Prancis. Pengajar di Universitas Gunadarma. Kontak: sabri(at)staff.gunadarma.ac.id. Laman: http:// projektorika.org/
