Belajar Math - Counting: Sum Rule & Product Rule
Product rule (opsi A × opsi B) dan sum rule (A atau B, saling lepas) adalah prinsip dasar menghitung kombinasi — fondasi untuk analisis kompleksitas brute-force, akses space password, dan complexity analysis.
#Pendahuluan
Setelah di episode 9 kita mempelajari proof techniques — termasuk induction yang berkaitan erat dengan rekursi — pada episode ini kita masuk ke combinatorics: cabang matematika yang berurusan dengan menghitung. Tepatnya, kita mulai dari dua prinsip paling fundamental: product rule dan sum rule.
Mengapa counting penting untuk programmer? Karena ketika kalian menganalisis kompleksitas brute-force, kalian sedang menghitung jumlah kemungkinan. Ketika kalian menghitung akses space password, kalian sedang menggunakan product rule. Ketika kalian menentukan apakah algoritma tertentu feasible atau tidak, kalian sedang menghitung. Keterampilan menghitung secara formal membuat kalian bisa memprediksi kompleksitas tanpa menjalankan kode.
#Product Rule (Aturan Perkalian)
#Definisi
Jika ada pilihan A dengan m opsi dan pilihan B dengan n opsi, maka total kombinasi A dan B bersama-sama adalah m × n.
#Analogi Sederhana
Bayangkan kalian mau pakai baju dan celana. Ada 3 baju dan 2 celana. Total kombinasi: 3 × 2 = 6.
baju = ["Merah", "Biru", "Hijau"]
celana = ["Jeans", "Kargo"]
kombinasi = [(b, c) for b in baju for c in celana]
for k in kombinasi:
print(f" {k[0]} + {k[1]}")
print(f"Total: {len(kombinasi)} kombinasi") # 6#Nested Loop = Product Rule
Setiap nested loop adalah implementasi product rule:
# 3 loop bersarang: total iterasi = a × b × c
count = 0
for i in range(3): # 3 opsi
for j in range(4): # 4 opsi
for k in range(5): # 5 opsi
count += 1
print(f"Total iterasi: {count}") # 60 = 3 × 4 × 5
print(f"Complexity: O(n³) jika semua range size n")#Akses Space Password
Product rule secara langsung digunakan untuk menghitung brute-force space:
import math
# Password 4 karakter dari 62 kemungkinan (a-z, A-Z, 0-9)
CHARSET_SIZE = 62
LENGTH = 4
# Product rule: 62 × 62 × 62 × 62 = 62^4
akses_space = CHARSET_SIZE ** LENGTH
print(f"Password {LENGTH} karakter: {akses_space:,} kemungkinan")
print(f"= {akses_space / 1_000_000:.1f} juta")
# Jika bisa menguji 1 juta password/detik
waktu_detik = akses_space / 1_000_000
print(f"Waktu brute-force (1M/detik): {waktu_detik:,.0f} detik")
print(f"= {waktu_detik / 3600:.1f} jam")
# Untuk password 8 karakter
akses_8 = CHARSET_SIZE ** 8
waktu_8 = akses_8 / 1_000_000 / 3600 / 24 / 365
print(f"\nPassword 8 karakter: {akses_8:,} kemungkinan")
print(f"Brute-force: {waktu_8:,.0f} tahun!")#Sum Rule (Aturan Penjumlahan)
#Definisi
Jika ada pilihan A dengan m opsi DAN pilihan B dengan n opsi, dan kalian hanya bisa memilih satu dari keduanya (mutually exclusive), maka total opsi adalah m + n.
#Analogi Sederhana
Di menu restoran, ada 4 nasi dan 3 mie. Kalian hanya bisa memesan satu. Total: 4 + 3 = 7.
nasi = ["Nasi Goreng", "Nasi Kucing", "Nasi Uduk", "Nasi Pecel"]
mie = ["Mie Goreng", "Mie Rebus", "Mie Ayam"]
total_menu = len(nasi) + len(mie)
print(f"Total menu: {total_menu}") # 7
# Kombinasi: memilih SATU dari semua
semua = nasi + mie
print(f"Semua opsi: {semua}")#OR dalam Kode = Sum Rule
users = [
{"name": "Alice", "role": "admin"},
{"name": "Bob", "role": "editor"},
{"name": "Charlie", "role": "viewer"},
{"name": "Diana", "role": "admin"},
{"name": "Eve", "role": "editor"},
]
# Sum rule: jumlah admin + jumlah editor (mutually exclusive)
admin_count = sum(1 for u in users if u["role"] == "admin")
editor_count = sum(1 for u in users if u["role"] == "editor")
privileged = admin_count + editor_count
print(f"Admin: {admin_count}, Editor: {editor_count}")
print(f"Privileged (sum rule): {privileged}")#Menggabungkan Sum dan Product Rule
Dalam praktik, kedua aturan sering digabungkan:
# Sistem login: login via email ATAU username, lalu password
# Email: pilihan dari provider (gmail, yahoo, outlook) + domain
# Username: huruf + angka
# Product rule untuk email login
email_options = 3 * 10 # 3 provider × 10 domain
# Product rule untuk username login
username_options = 26 * 26 * 10 # 2 huruf × 10 angka (simplified)
# Sum rule: email ATAU username
login_options = email_options + username_options
print(f"Email login options: {email_options}")
print(f"Username login options: {username_options}")
print(f"Total login options: {login_options}")#Kompleksitas Brute-Force
import time
def brute_force_count(arr, target):
"""O(n) — single loop = sum rule (satu operasi per elemen)."""
for i, val in enumerate(arr):
if val == target:
return i
return -1
def nested_brute_force_count(matrix, target):
"""O(n²) — nested loop = product rule."""
for i, row in enumerate(matrix):
for j, val in enumerate(row):
if val == target:
return (i, j)
return None
# Bandingkan waktu
data = list(range(10_000_000))
start = time.perf_counter()
brute_force_count(data, 9_999_999)
t_linear = time.perf_counter() - start
matrix = [list(range(i*1000, (i+1)*1000)) for i in range(10000)]
start = time.perf_counter()
nested_brute_force_count(matrix, 9_999_999)
t_quad = time.perf_counter() - start
print(f"Linear O(n): {t_linear:.4f}s")
print(f"Quadratic O(n²): {t_quad:.4f}s")
print(f"Quadratic {t_quad/t_linear:.0f}x lebih lambat!")#Aplikasi: Permutation Sederhana
Product rule secara langsung menghitung jumlah permutation — urutan item:
from math import factorial
# 5 buku di rak: berapa cara menata ulang?
buku = 5
cara_tata = factorial(buku) # Product rule: 5 × 4 × 3 × 2 × 1
print(f"Cara menata {buku} buku: {cara_tata}")
# Jika hanya 3 dari 5 buku yang ditata
from math import perm
cara_3_dari_5 = perm(5, 3) # 5 × 4 × 3 = 60
print(f"Cara menata 3 dari {buku} buku: {cara_3_dari_5}")Tip
Product rule berlaku untuk pilihan yang harus dilakukan bersamaan (AND). Sum rule berlaku untuk pilihan yang salah satu (OR) dan mutually exclusive. Jika tidak mutually exclusive, gunakan inclusion-exclusion (episode 12).
#Penutup
Inti yang harus dibawa pulang:
- Product rule: pilihan bersamaan (AND) → kalikan opsi. Nested loop = product rule.
- Sum rule: pilihan saling lepas (OR, mutually exclusive) → jumlahkan opsi. OR dalam kode = sum rule.
- Akses space password menggunakan product rule:
charset^length. - Kompleksitas brute-force: linear loop = sum rule; nested loop = product rule.
- Kedua aturan sering digabungkan untuk analisis kompleksitas yang lebih realistis.
Di episode 11 selanjutnya kita akan mempelajari permutasi dan kombinasi — ketika urutan penting (permutasi) dan ketika urutan tidak penting (kombinasi). Product rule dan sum rule yang baru kalian kuasai adalah fondasi dari kedua konsep ini!