Generating Combinations

Menggerakkan Kombinasi dari sebuah himpunan S berarti mewujudkan himpunan C yang merupakan salah satu subhimpunan dari S.

Permasalahan umum dalam menggerakkan kombinasi adalah:

Diberikan sebuah himpunan S, tentukan:

Semua kombinasi yang mungkin dari himpunan S
Semua kombinasi r elemen dari himpunan S
Kombinasi r elemen dari himpunan S, pada indeks ke-i berdasarkan urutan leksikografik

Daftar isi

1 Menggerakkan Semua Kombinasi yang Mungkin
2 Menggerakkan Semua Kombinasi r elemen
3 Kombinasi ke-i dari r elemen
4 Lihat pula

Menggerakkan Semua Kombinasi yang Mungkin

Cara paling gampang untuk menggerakkan semua kombinasi (himpunan bagian) yang mungkin adalah dengan menggunakan representasi biner.

Tiap himpunan anggota {a, b, c, d} yang berisi 4 elemen, dapat direpresentasikan sebagai bilangan biner 4 digit, yang masing masing bit menunjuk mempunyai tidaknya elemen tersebut dalam himpunan. Himpunan {a, c} misalnya, dapat direpresentasikan dengan bilangan biner 1010 (atau desimal 10), jika elemen-elemen a, b, c, d terus-menerus diwakili oleh bit ke 3, 2, 1, dan 0.

Himpunan : { a, b, c, d }
Representasi biner : 1 0 1 0
Himpunan anggota : { a, c }

Representasi seperti ini memetakan tiap jenis kombinasi dengan tepat satu bilangan asli. Daftar berikut menunjuk semua kombinasi dari {a, b, c, d} beserta representasi binernya.

Himpunan Biner Desimal --------------- ------ ------- { } 0000 0 { a } 1000 8 { b } 0100 4 { c } 0010 2 { d } 0001 1 { a, b } 1100 12 { a, c } 1010 10 { a, d } 1001 9 { b, c } 0110 6 { b, d } 0101 5 { c, d } 0011 3 { a, b, c } 1110 14 { a, b, d } 1101 13 { a, c, d } 1011 11 { b, c, d } 0111 7 { a, b, c, d } 1111 15

Berdasarkan ini kami dapat menyusun sebuah algoritma yang akan mewujudkan semua kombinasi yang mungkin, berdasarkan bilangan asli yang berkaitan dengannya. Banyak kombinasi yang mungkin untuk sebuah himpunan S, berdasarkan dengan banyaknya elemen himpunan kuasa dari S, adalah:

$|mathcal{P}(S)| = 2^{|S|}$

Maka bilangan asli yang berkaitan dengan tiap himpunan anggota S adalah tidak kekurangan dalam jangkauan $0 ... .. 2^{|S|}-1$ .

Berikut ini adalah pseudocode-nya:

Diberikan sebuah himpunan S: n = banyak elemen S for i = 0 to 2ⁿ-1 begin B = representasi bilangan i dalam bangun-bangun biner S' = { } for j = 0 to n-1 begin if digit ke-j dari B adalah 1 then tambahkan kepada S' elemen ke-j dari S end Tuliskan S' end

Kelemahan algoritma ini adalah daftar kombinasi yang diproduksi tidak otomatis dalam kondisi terurut secara leksikografik.

Menggerakkan Semua Kombinasi r elemen

Kombinasi ke-i dari r elemen

Lihat pula

Kombinasi
Kombinadik

Sumber :
m.andrafarm.com, pasar.kuliah-karyawan.com, wiki.edunitas.com, id.wikipedia.org, dan sebagainya.