Belajar Math - Permutasi & Kombinasi
Permutasi nPr (urutan penting) dan kombinasi nCr (urutan tidak penting) serta factorial adalah alat untuk menghitung scheduling, insertion order, subset selection, dan search space size — dari feature flags combinatorial testing hingga analisis kompleksitas.
#Pendahuluan
Setelah di episode 10 kita mempelajari product rule dan sum rule — prinsip dasar menghitung — pada episode ini kita menggunakannya untuk menghitung permutasi (urutan penting) dan kombinasi (urutan tidak penting). Ini adalah dua cara paling umum menghitung jumlah cara memilih dan menata item.
Mengapa permutasi dan kombinasi penting? Karena dalam programming kita sering perlu menghitung jumlah kemungkinan: berapa cara menata task dalam scheduling? Berapa cara memilih subset fitur untuk testing? Berapa ukuran search space untuk brute-force? Memahami formula memungkinkan kita menghitung tanpa enumerasi — mengubah O(n!) menjadi O(1).
#Factorial (n!)
Factorial adalah fondasi dari permutasi: n! = n × (n-1) × (n-2) × ... × 2 × 1.
import math
# Factorial manual
def faktorial(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
# Bandingkan dengan math.factorial
for n in [5, 10, 15, 20]:
manual = faktorial(n)
built_in = math.factorial(n)
print(f"{n}! = {manual:,} (manual: {manual == built_in})")
# Pertumbuhan factorial — sangat cepat!
print(f"\n20! = {math.factorial(20):,}")
print(f"50! = {math.factorial(50):.2e}") #科学记数法#Permutasi (nPr)
#Definisi
Permutasi adalah jumlah cara menata r item dari n item yang berbeda, di mana urutan penting.
Formula: P(n, r) = n! / (n-r)!
#Kapan Permutasi?
- Task scheduling: urutan eksekusi berpengaruh
- Password generation: urutan karakter menentukan password
- Tournament ranking: urutan juara 1, 2, 3 berbeda
from math import perm, factorial
# 3 dari 5 buku ditata di rak — urutan penting
n, r = 5, 3
permutasi = perm(n, r)
manual = factorial(n) // factorial(n - r)
print(f"P({n},{r}) = {permutasi}") # 60
print(f"Manual: {n}!/{n-r}! = {manual}")
# Contoh: berapa password 4 digit dari 10 angka? (urutan penting)
password_perms = perm(10, 4)
print(f"\nPassword 4 digit dari 10 angka: {password_perms:,}")
# Scheduling: 4 task, 2 slot waktu
task_perms = perm(4, 2)
print(f"Cara jadwalkan 4 task di 2 slot: {task_perms}")#Visual: Permutasi 3 item dari [A, B, C, D]
P(4,3) = 24 kemungkinan:
ABC, ACB, BAC, BCA, CAB, CBA
ABD, ADB, BAD, BDA, DAB, DBA
ACD, ADC, CAD, CDA, DAC, DCA
BCD, BDC, CBD, CDB, DBC, DCB#Kombinasi (nCr)
#Definisi
Kombinasi adalah jumlah cara memilih r item dari n item yang berbeda, di mana urutan tidak penting.
Formula: C(n, r) = n! / (r! × (n-r)!)
#Kapan Kombinasi?
- Subset selection: memilih fitur untuk testing
- Lottery: memilih angka (urutan tidak penting)
- Team formation: memilih anggota tim
from math import comb
# Pilih 3 dari 5 buku — urutan tidak penting
n, r = 5, 3
kombinasi = comb(n, r)
manual = math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
print(f"C({n},{r}) = {kombinasi}") # 10
print(f"Manual: {n}!/({r}!×{n-r}!) = {manual}")
# Feature flags: pilih 3 dari 7 fitur untuk A/B testing
fitur = 7
dipilih = 3
testing_kombinasi = comb(fitur, dipilih)
print(f"\nCara memilih {dipilih} dari {fitur} fitur: {testing_kombinasi}")
# Lottery: pilih 6 dari 45 angka
lottery = comb(45, 6)
print(f"Lottery 6/45: {lottery:,} kemungkinan")#Visual: Kombinasi 3 item dari [A, B, C, D]
C(4,3) = 4 kemungkinan (urutan tidak penting):
{A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}#Perbedaan Permutasi vs Kombinasi
from itertools import permutations, combinations
items = ["A", "B", "C", "D"]
r = 3
# Permutasi: urutan penting
perms = list(permutations(items, r))
print(f"P({len(items)},{r}) = {len(perms)} permutasi")
# Kombinasi: urutan tidak penting
combs = list(combinations(items, r))
print(f"C({len(items)},{r}) = {len(combs)} kombinasi")
# Hubungan: P(n,r) = C(n,r) × r!
print(f"\nVerifikasi: {len(combs)} × {r}! = {len(combs) * math.factorial(r)}")
print(f"P({len(items)},{r}) = {len(perms)}")
print(f"Sama? {len(combs) * math.factorial(r) == len(perms)}")#Aplikasi dalam Programming
#Combinatorial Testing
from itertools import combinations
features = ["dark-mode", "notifications", "analytics", "export", "api"]
test_budget = 3 # Hanya bisa test 3 fitur
# Kombinasi: pilih test_budget dari semua fitur
test_plans = list(combinations(features, test_budget))
print(f"Test plans ({test_budget} dari {len(features)} fitur):")
for i, plan in enumerate(test_plans, 1):
print(f" Plan {i}: {plan}")
print(f"Total: {len(test_plans)} test plan")#Search Space Analysis
from math import comb, perm
# Brute-force 4-char password dari 62 charset
charset = 62
length = 4
total_space = charset ** length # Product rule: 62^4
print(f"Search space ({length} char, {charset} charset): {total_space:,}")
# Jika urutan karakter tidak penting (kombinasi)
# Ini TIDAK berlaku untuk password karena urutan penting!
# Ini hanya ilustrasi perbedaan
comb_space = comb(charset + length - 1, length)
print(f"Jika urutan tidak penting: {comb_space:,}")
print(f"Perbedaan: {total_space / comb_space:.0f}x lebih kecil")#Scheduling Optimization
from itertools import permutations
tasks = ["Deploy", "Test", "Review", "Build"]
# Semua kemungkinan urutan
all_orders = list(permutations(tasks))
print(f"Total urutan: {len(all_orders)}")
# Filter: Build harus sebelum Deploy
valid_orders = [
order for order in all_orders
if order.index("Build") < order.index("Deploy")
]
print(f"Urutan valid (Build < Deploy): {len(valid_orders)}")
print(f"\n5 urutan valid pertama:")
for order in valid_orders[:5]:
print(f" {' → '.join(order)}")Note
Permutasi selalu ≥ kombinasi untuk n dan r yang sama, karena permutasi menghitung semua urutan sedangkan kombinasi hanya menghitung subset. Hubungan: P(n,r) = C(n,r) × r!. Gunakan permutasi ketika urutan berpengaruh, kombinasi ketika tidak.
#Penutup
Inti yang harus dibawa pulang:
- Factorial
n!adalah fondasi permutasi — tumbuh sangat cepat (20! ≈ 2.4 × 10¹⁸). - Permutasi P(n,r) = n!/(n-r)! — urutan penting. Untuk scheduling, password, ranking.
- Kombinasi C(n,r) = n!/(r!×(n-r)!) — urutan tidak penting. Untuk subset, feature flags, lottery.
- Hubungan: P(n,r) = C(n,r) × r! — permutasi selalu ≥ kombinasi.
- Gunakan
math.perm()danmath.comb()di Python untuk menghitung tanpa enumerasi.
Di episode 12 selanjutnya kita akan mempelajari Pigeonhole Principle dan Inclusion-Exclusion — dua prinsip counting lanjutan yang muncul dalam collision detection, Bloom filter, dan birthday paradox. Kombinasi yang baru kalian kuasai adalah fondasi untuk memahami mengapa collision tidak bisa dihindari!