Énumération des sous-ensembles par masque binaire
Parcourir tous les sous-ensembles au moyen d’entiers
Énumération des sous-ensembles par masque binaire est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Les sous-ensembles comme nombres
Chaque sous-ensemble de n éléments correspond à un seul entier. Comptez à partir de 0, et les bits de chaque nombre indiquent exactement quels éléments sont inclus. 🙂
Combien existe-t-il de sous-ensembles
Un ensemble de n éléments possède 2^n sous-ensembles. Ainsi, parcourir les entiers de 0 à 2^n moins 1 visite chaque sous-ensemble exactement une fois.
for mask in range(1 << n):
pass # mask is one subset1 << n est le nombre
Le décalage 1 << n vaut 2 à la puissance n. C’est une manière claire et rapide d’écrire la borne supérieure de votre boucle sur les sous-ensembles.
Lire le bit i
Pour vérifier si l’élément i appartient au sous-ensemble, testez son bit avec un masque et 1 décalé vers la gauche de i. Un résultat non nul signifie qu’il est inclus.
if mask & (1 << i):
take(items[i])Construire la liste choisie
Parcourez chaque position de bit et rassemblez les éléments dont le bit est activé. Vous transformez ainsi un masque en sous-ensemble concret représenté par celui-ci.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Sous-ensembles vide et complet
Le masque 0 représente le sous-ensemble vide, tandis que le masque composé uniquement de 1 représente l’ensemble complet. Vous obtenez gratuitement les deux puisque votre boucle parcourt toutes les valeurs.
Additionner sur un sous-ensemble
Dans la boucle, utilisez add pour totaliser les éléments choisis et évaluer chaque sous-ensemble. C’est le cœur de nombreuses petites solutions par force brute.
total = sum(v[i] for i in range(n) if mask & (1 << i))Compter les bits activés
Le nombre d’éléments choisis correspond au nombre de bits à 1 du masque. En Python, bin(mask).count('1') le donne instantanément.
size = bin(mask).count("1")Surveiller la limite
Puisqu’il y a 2^n sous-ensembles, cette technique ne convient qu’aux petites valeurs de n. En pratique, n égal à 20 constitue la limite supérieure pour une énumération complète.
Pourquoi les masques de bits sont efficaces
Une seule boucle sur un entier remplace des boucles imbriquées complexes, et les opérations sur les bits sont rapides. Le code reste court, clair et facile à tester.
Un schéma réutilisable
Parcourez le masque, décodez ses bits, évaluez le sous-ensemble et conservez le meilleur résultat. Mémorisez ce modèle et de nombreux problèmes de sous-ensembles deviennent routiniers.
Vérification rapide
Vous voulez vérifier si l’élément i est inclus dans le sous-ensemble codé par le masque.
Récapitulatif
Parcourez un masque de 0 à 2^n moins 1, lisez les bits avec le masque et 1 décalé vers la gauche, puis évaluez chaque sous-ensemble. C’est une méthode claire de force brute pour les petites valeurs de n. 🚀
Questions Fréquemment Posées
La leçon « Énumération des sous-ensembles par masque binaire » est-elle gratuite ?
Oui — le texte complet de « Énumération des sous-ensembles par masque binaire » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Énumération des sous-ensembles par masque binaire » ?
Parcourir tous les sous-ensembles au moyen d’entiers Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Énumération des sous-ensembles par masque binaire » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- La force brute est une stratégie valable
- Énumérer avec itertools
- Énumération des sous-ensembles par masque binaire
- Réduire intelligemment l’espace de recherche