Soal-soal kombinasi

Soal kombinasi menuntut backtracking yang lebih hemat daripada templat dasar. Topik ini menambahkan dua kebiasaan pada templat pilih, jelajahi, dan batalkan pilihan, yaitu indeks mulai yang mencegah satu kombinasi dihitung berkali-kali serta pemangkasan yang menghentikan cabang yang sudah pasti gagal. Kombinasi jumlah menjadi contoh utamanya, lengkap dengan penghitung simpul yang membuktikan efek pemangkasannya secara terukur.

Kombinasi dan indeks mulai#

Kombinasi memperlakukan urutan sebagai tidak penting, sehingga (1, 2) dan (2, 1) adalah satu jawaban yang sama. Cara termurah untuk menegakkan aturan itu adalah memaksa setiap pilihan bergerak maju: tingkat berikutnya hanya boleh memilih elemen dengan indeks lebih besar dari pilihan terakhir. Dengan satu parameter mulai, setiap kombinasi dilalui tepat satu kali, yaitu pada satu-satunya urutan indeks yang menaik.

Perbandingan dengan permutasi terlihat langsung pada angkanya. $\binom{4}{2}$ menghasilkan enam jawaban, sedangkan permutasi dua posisi dari empat anggota menghasilkan dua belas. Fungsi berikut memakai parameter mulai untuk menegakkan perbedaan itu:

def kombinasi(item, k, mulai=0, jalur=None):
    # kombinasi: urutan tidak penting, lanjut dari indeks berikutnya
    if jalur is None:
        jalur = []
    if len(jalur) == k:
        return [tuple(jalur)]
    hasil = []
    for i in range(mulai, len(item)):
        jalur.append(item[i])
        hasil.extend(kombinasi(item, k, i + 1, jalur))
        jalur.pop()
    return hasil

print('kombinasi C(4,2):', kombinasi([1, 2, 3, 4], 2))

kombinasi C(4,2): [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

Parameter mulai juga menjawab varian yang mengizinkan elemen dipakai ulang: kirim i, bukan i + 1, pada pemanggilan berikutnya, sehingga kandidat yang sama masih boleh dipilih lagi di tingkat bawah. Perhatikan pula bahwa daftar masukan pada contoh sudah terurut. Pemangkasan pada bagian berikut bergantung pada urutan ini, sehingga mengurutkan masukan terlebih dahulu adalah langkah pembuka yang wajib dilakukan. Pengurutan ini juga membuat keluaran fungsi terurut rapi tanpa langkah tambahan apa pun.

Pemangkasan cabang yang sia-sia#

Pemangkasan (pruning) adalah keputusan untuk tidak menuruni cabang yang sudah pasti tidak menghasilkan jawaban. Pada kombinasi jumlah, sisa target adalah informasinya. Bila kandidat terkecil yang tersisa sudah lebih besar dari sisa target, seluruh kandidat berikutnya juga pasti gagal karena daftarnya terurut. Dalam keadaan itu, perulangannya boleh dihentikan dengan break, bukan sekadar dilompati dengan continue. Satu break menghemat seluruh subpohon di belakangnya.

Efek pemangkasan diukur dengan penghitung simpul, yaitu banyaknya pemanggilan fungsi penelusuran yang benar-benar terjadi. Gambar berikut membandingkan versi tanpa pemangkasan dan versi dengan pemangkasan pada kandidat [2, 3, 5, 7] dengan target 7:

Jumlah simpul turun dari 28 menjadi 11 pada masukan kecil ini, dan rasionya makin lebar pada masukan yang lebih besar. Pemangkasan tidak mengubah himpunan jawaban, hanya jalan yang dilalui untuk mengumpulkannya. Angka pada diagram dihitung langsung oleh kode yang disertakan, sehingga perbandingannya dapat diulang kapan saja. Aturan umumnya singkat: pindahkan sebanyak mungkin pengetahuan tentang soal ke titik teratas cabang, sebelum pekerjaan sia-sia sempat menumpuk pada stack.

Kombinasi jumlah dengan penghitung simpul#

Berkas berikut memuat kedua versi berdampingan. Versi pertama mengurutkan kandidat lalu memangkas dengan break, sedangkan versi kedua hanya berhenti ketika sisanya negatif. Keduanya mencari kombinasi yang menjumlahkan ke 7 dari kandidat [2, 3, 5, 7], dengan aturan satu elemen boleh dipakai ulang:

# kombinasi-jumlah.py
# Combination-sum dengan dan tanpa pemangkasan, dibandingkan lewat penghitung simpul.

def cari(kandidat, target):
    # versi dengan pemangkasan: cabang yang pasti melebihi target dihentikan
    kandidat = sorted(kandidat)
    hasil, jalur = [], []
    simpul = 0

    def telusuri(mulai, sisa):
        nonlocal simpul
        simpul += 1
        if sisa == 0:
            hasil.append(tuple(jalur))
            return
        for i in range(mulai, len(kandidat)):
            if kandidat[i] > sisa:
                break   # pemangkasan: elemen berikutnya makin besar, tidak ada harapan
            jalur.append(kandidat[i])
            telusuri(i, sisa - kandidat[i])   # i, bukan i + 1, agar boleh dipakai ulang
            jalur.pop()

    telusuri(0, target)
    return hasil, simpul

def cari_tanpa_pangkas(kandidat, target):
    # versi tanpa pemangkasan: semua cabang dijelajahi sampai sisa negatif
    hasil, jalur = [], []
    simpul = 0

    def telusuri(mulai, sisa):
        nonlocal simpul
        simpul += 1
        if sisa == 0:
            hasil.append(tuple(jalur))
            return
        if sisa < 0:
            return
        for i in range(mulai, len(kandidat)):
            jalur.append(kandidat[i])
            telusuri(i, sisa - kandidat[i])
            jalur.pop()

    telusuri(0, target)
    return hasil, simpul

hasil_a, simpul_a = cari([2, 3, 5, 7], 7)
hasil_b, simpul_b = cari_tanpa_pangkas([2, 3, 5, 7], 7)
print("kombinasi jumlah 7:", sorted(hasil_a))
print("simpul dengan pemangkasan :", simpul_a)
print("simpul tanpa pemangkasan  :", simpul_b)
print("hasil kedua versi sama    :", sorted(hasil_a) == sorted(hasil_b))

kombinasi jumlah 7: [(2, 2, 3), (2, 5), (7,)]
simpul dengan pemangkasan : 11
simpul tanpa pemangkasan  : 28
hasil kedua versi sama    : True

Tiga jawaban ditemukan, yaitu 2+2+3, 2+5, dan 7 itu sendiri. Penghitung simpul dideklarasikan dengan nonlocal dan bertambah di baris pertama penelusuran, sehingga angkanya mencakup simpul jawaban maupun simpul yang gagal. Teknik penghitungan sederhana ini layak dipertahankan saat mengembangkan pemangkasan baru, karena penurunan jumlah simpul dapat dibandingkan langsung tanpa perlu mengubah bentuk jawabannya.

Perhatikan kapan break bekerja dibandingkan continue. Pada kandidat 5 dengan sisa 4, perbandingan kandidat[i] > sisa langsung menutup perulangan karena seluruh kandidat berikutnya juga lebih besar, sedangkan continue hanya melompati satu kandidat lalu tetap mencoba yang lain. Pada target 7 yang kecil, selisihnya tampak sepele, tetapi subpohon yang terhemat tumbuh eksponensial seiring target dan banyak kandidat bertambah.

Kesalahan umum#

Kesalahan pertama adalah memakai i + 1 pada soal yang mengizinkan elemen dipakai ulang, atau sebaliknya memakai i pada soal yang melarangnya. Gejalanya jawaban hilang, atau muncul kombinasi tak sah yang mengulang elemen yang sama. Tetapkan aturan pemakaian ulangnya di awal pengerjaan, lalu biarkan satu parameter mulai yang mengurusnya sampai selesai.

Kesalahan kedua adalah duplikasi hasil pada masukan yang memuat elemen kembar, misalnya [2, 2, 3]. Penangkalnya dua lapis: urutkan masukan agar kembar itu berdampingan, lalu di dalam perulangan, lewati kandidat yang sama dengan kandidat sebelumnya pada tingkat yang sama. Tanpa kedua lapis itu, kombinasi yang sama tercetak beberapa kali dan pemeriksa soal menolak jawabannya.

Kesalahan ketiga adalah memangkas tanpa mengurutkan masukan terlebih dahulu. Perbandingan kandidat[i] > sisa hanya sah pada daftar terurut, karena keputusan break mengasumsikan seluruh kandidat berikutnya tidak lebih kecil. Pada daftar acak, pemangkasan yang sama diam-diam membuang jawaban yang sebenarnya, dan hasilnya tampak benar pada sebagian masukan saja.

Ringkasan#

• Parameter mulai menegakkan urutan menaik sehingga satu kombinasi dilalui tepat satu kali.
• Mengirim i alih-alih i + 1 mengizinkan satu elemen dipakai ulang pada tingkat berikutnya.
• Pemangkasan dengan break pada daftar terurut menghentikan cabang yang sisa targetnya sudah lebih kecil dari kandidat.
• Penghitung simpul membuktikan efek pemangkasan secara terukur, dari 28 simpul turun ke 11 pada contoh target 7.

Referensi#

• Backtracking — Wikipedia — Pembahasan pemangkasan ruang pencarian sebagai inti efisiensi backtracking.
• NeetCode Roadmap — Daftar soal latihan bertingkat yang memuat kombinasi, combination sum, dan varian duplikatnya.