Bitmask Alt Küme Numaralandırması

n öğenin her alt kümesi tek bir tam sayıyla eşleştirilebilir. 0'dan başlayarak sayın; her sayının bitleri, hangi öğelerin dahil edildiğini tam olarak belirler. 🙂

n öğeden oluşan bir kümenin 2^n alt kümesi vardır. Bu nedenle bir tamsayıyı 0'dan 2^n eksi 1'e kadar döndürmek, her alt kümeyi tam olarak bir kez ziyaret eder.

1 << n ötelemesi, 2 üzeri n'e eşittir. Alt küme döngünüzün üst sınırını yazmanın temiz ve hızlı yoludur.

i öğesinin alt kümede olup olmadığını öğrenmek için maskeyi ve i kadar sola kaydırılmış 1'i kullanarak bit değerini sınayın. Sıfır olmayan bir sonuç, öğenin dahil edildiği anlamına gelir.

Her bit konumunu inceleyin ve bit değeri ayarlanmış olan öğeleri toplayın. Böylece tek bir maske, temsil ettiği somut alt kümeye dönüşür.

Maske 0, boş alt kümedir; tüm bitleri 1 olan maske ise tam kümedir. Döngünüz her değeri kapsadığı için ikisi de kendiliğinden elde edilir.

Döngünün içinde seçilen öğeleri toplayarak her alt kümeye puan verin. Bu, birçok küçük kaba kuvvet çözümünün temelidir.

Seçilen öğelerin sayısı, maskede 1 olan bitlerin sayısına eşittir. Python'da bin(mask).count('1') bunu anında verir.

2^n alt küme bulunduğundan bu teknik yalnızca küçük n değerleri için uygundur. Tümünü listelemek için n'nin yaklaşık 20 olması, pratikteki üst sınırdır.

Tek bir tamsayı döngüsü, karmaşık iç içe döngülerin yerini alır ve bit işlemleri hızlıdır. Kod kısa, anlaşılır ve sınanması kolay kalır.

Maskeyi döndürün, bitlerini çözümleyin, alt kümeye puan verin ve en iyiyi izleyin. Bu şablonu ezberlerseniz birçok alt küme problemi rutin hâle gelir.

mask ile kodlanan alt kümeye i öğesinin dahil edilip edilmediğini sınamak istiyorsunuz.

Bir maskeyi 0'dan 2^n eksi 1'e kadar döndürün, bitleri maske ile sola kaydırılmış 1'i kullanarak okuyun ve her alt kümeye puan verin. Bu, küçük n değerleri için temiz bir kaba kuvvet yöntemidir. 🚀