Alt Kümeleri Üretmek

#Nasıl çalışır?

n elemanlı bir kümenin 2ⁿ alt kümesi vardır; çünkü her eleman için iki seçenek bulunur: ya alt kümeye girer ya girmez. Bu kararlar ikili bir karar ağacı oluşturur.

Geri izlemeyle her seviyede bir eleman için karar verilir. Önce eleman alınır ve kalan elemanlar için devam edilir; o dal bitince eleman çıkarılır (geri alınır) ve elemansız dal denenir. Ağacın her yaprağı bir alt kümedir.

Aynı kalıp, kısıt eklenince güçlü bir araca dönüşür: örneğin toplamı belirli bir değere eşit alt kümeleri ararken toplam zaten aşıldıysa o dal hiç açılmaz (budama).

#Kendin dene

#Adım adım

1. 01İlk elemandan başla, seçilenler listesi boş olsun.
2. 02Elemanı listeye ekle ve bir sonraki elemana geç.
3. 03O dal bitince elemanı listeden çıkar ve elemansız devam et.
4. 04Tüm elemanlar için karar verildiğinde (yaprak) listeyi bir alt küme olarak kaydet.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def subsets(items: list) -> list:
    out, chosen = [], []

    def visit(i: int) -> None:
        if i == len(items):
            out.append(list(chosen))
            return
        chosen.append(items[i])  # take items[i]
        visit(i + 1)
        chosen.pop()             # leave it (backtrack)
        visit(i + 1)

    visit(0)
    return out


for s in subsets([1, 2, 3]):
    print("{" + ", ".join(map(str, s)) + "}")

#Karmaşıklık

Her alt kümeyi yazmak O(n) sürdüğü için toplam O(n · 2ⁿ)'dir; çıktının kendisi bu kadar büyük olduğundan daha hızlısı mümkün değildir. Alternatif olarak 0'dan 2ⁿ − 1'e kadar sayılar bit maskesi olarak kullanılabilir: i. bit 1 ise i. eleman alt kümededir.

#Ne zaman kullanılır?

Tüm kombinasyonların denenmesi gereken küçük problemler: alt küme toplamı, takım seçimi, özellik seçimi, kombinasyonel testler ve bulmacalarda arama. Eleman sayısı büyüdükçe 2ⁿ hızla büyüdüğü için budama ya da DP gerekir.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• N-Vezir Problemi
• Permütasyonları Üretmek