Subhimpunan dan permutasi

Banyak soal pencarian jawaban menuntut pembangkitan semua kandidat, bukan sekadar satu jawaban. Topik ini membungkus pola itu menjadi satu templat backtracking dengan tiga gerakan, yaitu pilih, jelajahi, dan batalkan pilihan. Templat yang sama dijalankan pada dua soal dasar, subhimpunan dan permutasi, sehingga perbedaan keduanya terlihat sebagai perbedaan keputusan, bukan perbedaan kerangka kode.

Templat pilih, jelajahi, batalkan pilihan#

Backtracking membangun jawaban sedikit demi sedikit pada sebuah list yang disebut jalur (path). Tiga gerakannya berulang pada setiap tingkat keputusan: pilih satu kandidat dan taruh di jalur, jelajahi dengan memanggil fungsi penelusuran untuk tingkat berikutnya, lalu batalkan pilihan dengan mengeluarkan kandidat dari jalur. Pembatalan inilah yang membedakan backtracking dari perulangan biasa, karena satu list jalur yang sama dipakai ulang untuk semua kandidat tanpa menyalin isi list berulang kali.

Gerakan ketiga paling sering terlewat pada penulisan pertama, dan akibatnya nyata. Jalur membawa sisa pilihan dari cabang lain, hasil menjadi ganda atau kacau, dan jumlah jawabannya tidak sesuai perhitungan. Gambar berikut merangkum siklus tiga gerakan tersebut:

Satu siklus menghasilkan satu cabang pohon pencarian, dan seluruh pencarian adalah siklus yang diulang pada setiap kandidat yang sah. Kerangkanya selalu sama antarsoal, sehingga perbedaannya tinggal menetap di dua tempat, yaitu daftar kandidat yang boleh dipilih dan syarat ketika jalur dianggap selesai. Dua bagian berikut mengisi kedua tempat itu untuk subhimpunan dan permutasi, dengan satu berkas kode yang menampung keduanya.

Subhimpunan dengan keputusan masuk atau lewati#

Subhimpunan dari n elemen berjumlah $2^n$, karena setiap elemen punya dua nasib, masuk ke jalur atau tidak. Pada tingkat ke-i, kandidatnya hanya satu, yaitu item[i], dan keputusannya dicatat dengan menambahkan elemen itu ke jalur sebelum pemanggilan turun ke i+1. Jalur dianggap selesai ketika i mencapai panjang masukan, dan jalur utuh itu disalin ke hasil dengan tuple(jalur) agar tidak berubah lagi.

# templat.py
# Satu templat, dua soal: pilih, jelajahi, batalkan pilihan.

def subhimpunan(item):
    # subhimpunan: keputusan masuk atau tidak untuk setiap elemen
    hasil, jalur = [], []

    def telusuri(i):
        if i == len(item):
            hasil.append(tuple(jalur))      # kasus dasar: jalur utuh dicatat
            return
        jalur.append(item[i])               # pilih: masukkan item[i]
        telusuri(i + 1)                     # jelajahi cabang dengan item[i]
        jalur.pop()                         # batalkan pilihan
        telusuri(i + 1)                     # jelajahi cabang tanpa item[i]

    telusuri(0)
    return hasil

def permutasi(item):
    # permutasi: tanda pakai mencegah satu elemen dipilih dua kali
    hasil, jalur = [], []
    pakai = [False] * len(item)

    def telusuri():
        if len(jalur) == len(item):
            hasil.append(tuple(jalur))
            return
        for i in range(len(item)):
            if pakai[i]:
                continue
            pakai[i] = True                 # pilih
            jalur.append(item[i])
            telusuri()                      # jelajahi
            jalur.pop()                     # batalkan pilihan
            pakai[i] = False

    telusuri()
    return hasil

data = ["a", "b", "c"]
print("subhimpunan (8):", sorted(subhimpunan(data)))
print("permutasi   (6):", sorted(permutasi(data)))

subhimpunan (8): [(), ('a',), ('a', 'b'), ('a', 'b', 'c'), ('a', 'c'), ('b',), ('b', 'c'), ('c',)]
permutasi   (6): [('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

Delapan subhimpunan muncul termasuk himpunan kosong, sesuai $2^3 = 8$. Perhatikan posisi jalur.pop() yang berada tepat di antara dua pemanggilan. Pemanggilan pertama mewarisi jalur dengan item[i] di dalamnya, sedangkan pemanggilan kedua mewarisi jalur yang sudah dikembalikan ke keadaan semula. Menambahkan pemanggilan kedua tanpa mengembalikan keadaan adalah sumber bug paling umum pada templat ini.

Bentuk keputusan ini penting dikenali karena muncul di banyak soal lain. Setiap kali kandidat pada satu tingkat hanya satu sementara tingkat berikutnya bergantung padanya, pohonnya berbentuk biner dan jumlah daunnya pangkat dua. Menghitung daun secara manual pada masukan tiga atau empat elemen menjadi cara cepat memeriksa kebenaran templat sebelum dipakai pada masukan yang lebih besar.

Permutasi dengan tanda pakai#

Permutasi dari n elemen berjumlah $n!$, karena setiap posisi pada jalur diperebutkan oleh elemen yang belum terpakai. Perbedaannya dengan subhimpunan ada pada daftar kandidatnya. Setiap tingkat boleh memilih semua elemen yang masih ditandai pakai[i] == False, bukan hanya satu elemen tertentu, sehingga pencacahnya berbentuk perulangan for di dalam fungsi penelusuran.

Setiap kandidat yang dipilih ditandai terpakai sebelum pemanggilan turun, lalu tandanya dilepas bersamaan dengan jalur.pop() setelah pemanggilan kembali. Dua pembatalan itu harus berpasangan dan berada pada jalur eksekusi yang sama, sebab tanda pakai yang tertinggal membuat elemen dianggap terpakai pada seluruh cabang berikutnya. Enam permutasi tercetak pada keluaran di atas sesuai $3! = 6$, dan angkanya membesar sangat cepat karena $10!$ sudah melampaui tiga juta. Karena pencacahnya sudah berbentuk perulangan, kandidat yang tidak sah sebaiknya dilompati sebelum pemilihan, bukan dibatalkan setelahnya. Dalam praktik, templat ini nyaris selalu dipakai bersama batasan tambahan yang memangkas cabang lebih awal sebelum jalur selesai dibangun.

Kesalahan umum#

Kesalahan pertama adalah pembatalan pilihan yang hilang, baik pada jalur maupun pada tanda pakai. Gejalanya khas, yaitu jumlah hasil terlalu sedikit, isi hasil tidak konsisten antarbaris, atau elemen terulang pada satu jalur. Perbaikannya mekanis: pasangkan setiap pilihan dengan pembatalannya, lalu periksa bahwa keduanya berada pada cabang eksekusi yang sama sebelum memanggil diri lagi. Menaruh jalur.pop() pada tempat yang salah, misalnya sesudah kedua pemanggilan sekaligus, tidak menyelamatkan keadaan cabang pertama dan bugnya tetap muncul.

Kesalahan kedua adalah menyalin atau tidak menyalin jalur pada waktu yang salah. Mencatat tuple(jalur) wajib dilakukan tepat ketika jalur dianggap selesai, karena list yang sama akan terus diubah setelahnya dan seluruh isi hasil berubah mengikuti, sehingga tercetak sebagai baris yang duplikat. Sebaliknya, menyalin jalur pada setiap tingkat memboroskan memori tanpa manfaat apa pun. Membandingkan panjang hasil dengan angka teoretis, $2^n$ untuk subhimpunan dan $n!$ untuk permutasi, menangkap kesalahan semacam ini dalam hitungan detik. Aturannya satu kalimat: salin saat menyimpan hasil, bagikan saat menelusuri.

Ringkasan#

• Templat backtracking terdiri atas tiga gerakan, yaitu pilih kandidat, jelajahi cabangnya, lalu batalkan pilihan.
• Subhimpunan berjumlah $2^n$ dan keputusannya masuk atau lewati per elemen, sedangkan permutasi berjumlah $n!$ dan memakai tanda pakai per elemen.
• jalur.pop() yang berada tepat di antara dua pemanggilan menjaga list jalur tetap dapat dipakai ulang.
• Salin jalur dengan tuple(jalur) hanya saat menyimpan hasil, bukan pada setiap tingkat penelusuran.

Referensi#

• itertools — Functions creating iterators for efficient looping — Python documentation — Fungsi bawaan permutations, combinations, dan product sebagai pembanding hasil templat manual.
• Backtracking — Wikipedia — Penjelasan umum backtracking sebagai penelusuran pohon ruang jawaban dengan pembatalan langkah.