Enumerering av delmängder med bitmasker
Iterera över alla delmängder via heltal
Enumerering av delmängder med bitmasker är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Delmängder som tal
Varje delmängd av n objekt kan motsvaras av ett enda heltal. Räkna upp från 0, så anger bitarna i varje tal exakt vilka objekt som ingår. 🙂
Hur många delmängder finns det
En mängd med n element har 2^n delmängder. Genom att låta ett heltal löpa från 0 till 2^n minus 1 besöker du därför varje delmängd exakt en gång.
for mask in range(1 << n):
pass # mask is one subset1 << n är antalet
Skiftningen 1 << n är lika med 2 upphöjt till n. Det är det tydliga och snabba sättet att skriva den övre gränsen för loopen över delmängderna.
Läs bit i
För att kontrollera om element i finns i delmängden testar du dess bit med masken och 1 vänsterskiftat med i. Ett resultat som inte är noll betyder att elementet ingår.
if mask & (1 << i):
take(items[i])Bygg listan över valda
Gå igenom varje bitposition och samla de element vars bit är satt. Då omvandlas en mask till den konkreta delmängd som den representerar.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Tomma och fullständiga mängder
Mask 0 är den tomma delmängden, och masken med enbart ettor representerar hela mängden. Båda får du automatiskt eftersom loopen täcker alla värden.
Summera över en delmängd
Summera de valda elementen i loopen för att poängsätta varje delmängd. Det här är kärnan i många små lösningar med brute force.
total = sum(v[i] for i in range(n) if mask & (1 << i))Räkna de satta bitarna
Antalet valda element motsvarar maskens popcount. I Python ger bin(mask).count('1') resultatet direkt.
size = bin(mask).count("1")Håll koll på gränsen
Eftersom det finns 2^n delmängder passar den här tekniken bara för små n. Runt n = 20 är den praktiska gränsen för fullständig uppräkning.
Varför bitmasker är överlägsna
En enda heltalsloop ersätter röriga nästlade loopar, och bitoperationer är snabba. Koden förblir kort, tydlig och enkel att testa.
Ett återanvändbart mönster
Iterera över mask, avkoda dess bitar, poängsätt delmängden och spara det bästa resultatet. Lär dig den här mallen utantill, så blir många problem med delmängder rutin.
Snabb kontroll
Du vill kontrollera om element i ingår i den delmängd som kodas av mask.
Sammanfattning
Låt en mask löpa från 0 till 2^n minus 1, läs av bitarna med mask och 1 vänsterskiftat, och poängsätt varje delmängd. Det är en tydlig brute force-metod för små n. 🚀
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Enumerering av delmängder med bitmasker” gratis?
Ja – hela texten till ”Enumerering av delmängder med bitmasker” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Enumerering av delmängder med bitmasker”?
Iterera över alla delmängder via heltal Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.
Hur lång tid tar lektionen ”Enumerering av delmängder med bitmasker”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Brute force är en giltig strategi
- Enumerera med itertools
- Enumerering av delmängder med bitmasker
- Minska sökrymden på ett smart sätt