Deelverzamelingen enumereren met bitmaskers

Elke deelverzameling van n items correspondeert met één geheel getal. Tel vanaf 0 omhoog; de bits van elk getal bepalen precies welke items erin zitten. 🙂

Een verzameling van n elementen heeft 2^n deelverzamelingen. Als je dus een geheel getal van 0 tot en met 2^n min 1 doorloopt, bezoek je elke deelverzameling precies één keer.

De verschuiving 1 << n is gelijk aan 2 tot de macht n. Dit is de duidelijke, snelle manier om de bovengrens van je lus over deelverzamelingen te schrijven.

Als je wilt bepalen of element i in de deelverzameling zit, controleer je zijn bit met een masker en 1 die i posities naar links is verschoven. Een resultaat dat niet nul is, betekent dat het element is opgenomen.

Doorloop elke bitpositie en verzamel de elementen waarvan de bit is ingesteld. Zo zet je één masker om in de concrete deelverzameling die het voorstelt.

Masker 0 is de lege deelverzameling en het masker met alleen enen is de volledige verzameling. Beide krijg je vanzelf, omdat je lus elke waarde doorloopt.

Tel binnen de lus de gekozen elementen op om elke deelverzameling een score te geven. Dit vormt de kern van veel kleine bruteforce-oplossingen.

Het aantal gekozen elementen is gelijk aan de popcount van het masker. In Python geeft bin(mask).count('1') dit meteen.

Omdat er 2^n deelverzamelingen zijn, werkt deze techniek alleen voor kleine n. Rond n gelijk aan 20 ligt de praktische grens voor volledige opsomming.

Met één lus over gehele getallen vervang je rommelige geneste lussen, en bitbewerkingen zijn snel. De code blijft kort, duidelijk en eenvoudig te controleren.

Doorloop het masker, decodeer de bits, geef de deelverzameling een score en houd de beste bij. Onthoud dit sjabloon en veel problemen met deelverzamelingen worden routine.

Doorloop een masker van 0 tot en met 2^n min 1, lees bits met het masker en 1 die naar links is verschoven, en geef elke deelverzameling een score. Dit is duidelijke bruteforce voor kleine n. 🚀