Kombinatorika

Penghitungan, permutasi, dan kombinasi.

Daftar isi

Menghitung kemungkinan dengan menyusun daftarnya satu per satu akan cepat menjadi tidak realistis, sedangkan kombinatorika menyediakan rumus penghitungan langsung. Topik ini membahas aturan perkalian dan penjumlahan, permutasi beserta faktorialnya, kombinasi, serta paradoks hari lahir yang menjelaskan peluang bentrok pada fungsi hash. Setelah topik ini dipahami, banyaknya susunan, pasangan, dan subkelompok dapat dihitung dengan rumus, diverifikasi lewat modul math, dan dihubungkan dengan analisis kompleksitas kode.

Aturan perkalian dan penjumlahan#

Aturan perkalian berlaku untuk pilihan yang dilakukan berurutan. Apabila langkah pertama memiliki $m$ kemungkinan dan langkah kedua memiliki $n$ kemungkinan, maka gabungan keduanya memiliki $m \times n$ kemungkinan. Sandi PIN empat digit memiliki $10 \times 10 \times 10 \times 10 = 10^4$ kemungkinan karena setiap posisi ditentukan secara mandiri. Aturan yang sama juga membangun pohon pilihan, yaitu setiap percabangan mengalikan jumlah daun dengan banyaknya cabangnya.

Aturan penjumlahan berlaku untuk pilihan yang saling meniadakan (mutually exclusive), yaitu apabila pilihan berasal dari kategori yang tidak dapat dipilih bersamaan. Gudang dengan 10 jenis kertas dan 15 jenis tinta menyimpan $10 + 15$ jenis barang apabila yang diambil tepat satu barang, tetapi $10 \times 15$ pasangan apabila yang diambil satu kertas dan satu tinta sekaligus. Membedakan kedua situasi ini adalah langkah pertama dalam setiap soal penghitungan, karena salah memilih aturan mengubah hasilnya sepenuhnya.

Permutasi dan faktorial#

Permutasi (permutation) menghitung banyaknya susunan berurutan dari sebagian objek. Menyusun jadwal piket dua posisi yang berbeda, yaitu pagi dan siang, dari enam petugas merupakan permutasi karena urutannya membedakan makna, sehingga petugas yang sama pada posisi yang berbeda dihitung dua kali.

P(n, r) = \frac{n!}{(n - r)!}

Nilai $P(6, 2) = \frac{6!}{4!} = 6 \times 5 = 30$ menyatakan tiga puluh susunan yang mungkin. Suku $n!$ yang dibaca faktorial (factorial) didefinisikan sebagai

n! = n \times (n-1) \times \cdots \times 1

Faktorial membesar dengan cepat, karena $10!$ sudah melewati 3,6 juta dan $20!$ melewati 2 kuintiliun. Pertumbuhan ini bukan sekadar fakta menarik, melainkan peringatan untuk kode, sebab algoritma yang menyenaraikan seluruh permutasi membutuhkan waktu sebanding dengan $n!$ .

Kombinasi#

Kombinasi (combination) menghitung banyaknya kelompok ketika urutan tidak diperhatikan. Memilih dua dari lima anggota untuk tugas piket tanpa posisi khusus adalah kombinasi, karena pasangan Ali lalu Budi sama dengan pasangan Budi lalu Ali.

C(n, r) = \binom{n}{r} = \frac{n!}{r!\,(n - r)!}

Setiap kelompok beranggota $r$ memiliki $r!$ susunan, sehingga hubungan keduanya adalah $P(n, r) = C(n, r) \times r!$ . Pohon pilihan berikut memperlihatkan hubungan tersebut pada kasus menyusun dua huruf dari tiga pilihan.

Pohon pilihan menyusun dua huruf dari tiga pilihan

Keenam daun pohon mewakili susunan berurutan, sedangkan tiga pasangan dihasilkan apabila daun AB dan BA digabungkan menjadi satu. Sifat simetri $C(n, r) = C(n, n-r)$ juga terbaca dari rumusnya, misalnya memilih dua dari lima sama banyaknya dengan meninggalkan tiga dari lima.

Menghitung dengan Python#

Modul math menyediakan ketiga fungsi penghitungan tersebut, sehingga setiap rumus dapat diverifikasi tanpa menulis perulangannya sendiri. Skrip berikut menghitung contoh-contoh pada bagian sebelumnya sekaligus memeriksa hubungan antara permutasi dan kombinasi.

python kombinatorika.py

"""Permutasi dan kombinasi dengan modul math beserta pemeriksaan hubungannya."""
import math

print("4!             :", math.factorial(4))
print("P(6, 2)        :", math.perm(6, 2))
print("C(6, 2)        :", math.comb(6, 2))
print("C(6, 2) * 2!   :", math.comb(6, 2) * math.factorial(2))
print("C(5, 2) piket  :", math.comb(5, 2))
print("pasangan n=1000:", math.comb(1000, 2))

text Keluaran

4!             : 24
P(6, 2)        : 30
C(6, 2)        : 15
C(6, 2) * 2!   : 30
C(5, 2) piket  : 10
pasangan n=1000: 499500

Baris keempat menegaskan bahwa $C(6, 2)$ dikalikan $2!$ mengembalikan $P(6, 2) = 30$ , sesuai hubungan pada bagian sebelumnya. Baris terakhir menghitung banyaknya pasangan dari 1.000 data sebesar 499500, angka yang kembali muncul ketika analisis kompleksitas dibahas di bagian akhir. Seluruh fungsi ini menghasilkan bilangan bulat yang besarnya sewenang-wenang, karena aritmetika bilangan bulat Python tidak meluber.

Paradoks hari lahir dan fungsi hash#

Paradoks hari lahir (birthday paradox) menanyakan banyaknya orang minimal dalam satu ruangan agar peluang dua orang berulang tahun pada hari yang sama melebihi separuh. Intuisi biasanya menjawab puluhan orang, sedangkan jawabannya hanya 23. Pertanyaan yang sama muncul pada fungsi hash, yaitu berapa banyak item yang dapat ditaburkan ke $n$ slot sebelum dua item berjatuhan pada slot yang sama.

P(\text{tanpa bentrok}) = \prod_{i=0}^{k-1} \frac{n - i}{n} \approx e^{-k(k-1)/(2n)}

Setiap item baru menghindari slot yang sudah terisi dengan peluang $\frac{n-i}{n}$ , dan hasil kalinya menyatakan peluang seluruh taburan bebas bentrok. Skrip berikut menghitungnya secara langsung untuk beberapa ukuran.

python paradoks-hash.py

"""Peluang bentrok pada fungsi hash mengikuti paradoks hari lahir."""
import math

def peluang_bentrok(banyak_item, ukuran_ruang):
    tanpa_bentrok = math.prod((ukuran_ruang - i) / ukuran_ruang for i in range(banyak_item))
    return round(1 - tanpa_bentrok, 4)

print("23 orang pada 365 hari       :", peluang_bentrok(23, 365))
print("75 orang pada 365 hari       :", peluang_bentrok(75, 365))
print("10.000 item pada hash 32 bit :", peluang_bentrok(10_000, 2**32))
print("77.000 item pada hash 32 bit :", peluang_bentrok(77_000, 2**32))

text Keluaran

23 orang pada 365 hari       : 0.5073
75 orang pada 365 hari       : 0.9997
10.000 item pada hash 32 bit : 0.0116
77.000 item pada hash 32 bit : 0.4985

Dua baris pertama menegaskan paradoksnya, karena 23 orang sudah melewati separuh dan 75 orang hampir pasti menghasilkan kembaran. Dua baris terakhir menerjemahkannya ke kode, yaitu hash 32 bit masih nyaman pada sepuluh ribu item dengan peluang bentrok $0.0116$ , tetapi pada 77 ribu item peluangnya sudah $0.4985$ . Ruang hash yang tampak sangat besar ternyata habis lebih cepat daripada kesan pertama, dan hampiran $e^{-k(k-1)/(2n)}$ menjadi perkiraan cepat tanpa perulangan untuk kasus yang jauh lebih besar.

Di mana hal ini ditemui dalam kode#

Analisis algoritma adalah bidang yang sering menggunakan kombinatorika. Perulangan bersarang yang membandingkan setiap data dengan data lainnya mengerjakan satu langkah per pasangan, sehingga biayanya $C(n, 2) = \frac{n(n-1)}{2}$ dan ditulis $O(n^2)$ . Untuk 1.000 data, jumlah pasangannya 499500 seperti pada keluaran skrip sebelumnya, dan angka itulah yang membuat algoritma berpasangan berjalan lambat pada data besar. Analisis kasus terburuk juga menghitung permutasi, karena pengurutan yang membandingkan seluruh susunan membutuhkan waktu sebanding dengan $n!$ .

Modul itertools menyediakan enumerasi yang menghasilkan satu kombinasi atau permutasi pada setiap langkah tanpa menyimpan semuanya di memori.

python Contoh: menghitung pasangan dengan kombinasi

import itertools

nama = ["ali", "budi", "citra", "dewi", "eka"]
pasangan = list(itertools.combinations(nama, 2))
print("banyaknya pasangan :", len(pasangan))
print("rumus C(5, 2)      :", 5 * 4 // 2)
print("contoh pasangan    :", pasangan[0], pasangan[-1])

text Keluaran

banyaknya pasangan : 10
rumus C(5, 2)      : 10
contoh pasangan    : ('ali', 'budi') ('dewi', 'eka')

Keluaran tersebut cocok dengan rumusnya, sehingga rumus dapat dipercaya sebagai alat hitung cepat dan itertools digunakan hanya apabila pasangannya benar-benar perlu disusuri. Pada basis data, pengekangan keunikan (unique constraint) pada dua kolom juga mencegah bentrok yang dihitung paradoks hari lahir, dan perancang indeks hash menggunakan hitungan yang sama untuk menakar ukuran ruangnya.

Ringkasan#

Aturan perkalian mengalikan pilihan berurutan yang mandiri, sedangkan aturan penjumlahan menjumlahkan pilihan dari kategori yang saling meniadakan.
Permutasi $P(n, r) = \frac{n!}{(n-r)!}$ membedakan urutan, kombinasi $C(n, r) = \frac{n!}{r!(n-r)!}$ mengabaikannya, dan keduanya terhubung oleh $P(n, r) = C(n, r) \times r!$ .
Modul math menyediakan factorial, perm, dan comb, sedangkan itertools menyusuri kandidatnya satu per satu tanpa memuat seluruhnya.
Paradoks hari lahir menunjukkan bahwa peluang bentrok hash naik mendekati satu jauh lebih cepat daripada ukuran ruangnya, dengan hampiran $1 - e^{-k(k-1)/(2n)}$ .

Referensi#

math — Python Software Foundation — Dokumentasi fungsi factorial, perm, dan comb yang digunakan seluruh perhitungan pada topik ini.
itertools — Python Software Foundation — Dokumentasi combinations dan permutations untuk menyusuri kandidat tanpa memuat semuanya.
Contemporary Mathematics — OpenStax — Buku teks terbuka dengan bab aturan penghitungan, permutasi, dan kombinasi.