تعداد المجموعات الجزئية بقناع البتات

يمكن ربط كل مجموعة جزئية من n عنصرًا بـ عدد صحيح واحد. ابدؤوا العد من 0، وستحدد بتات كل عدد العناصر الموجودة بالضبط. 🙂

تحتوي مجموعة مكوّنة من n عنصرًا على 2^n مجموعة جزئية. لذلك، فإن تكرار عدد صحيح من 0 إلى 2^n ناقص 1 يمرّ على كل مجموعة جزئية مرة واحدة بالضبط.

تساوي الإزاحة 1 << n العدد 2 مرفوعًا للقوة n. وهذه طريقة واضحة وسريعة لكتابة الحد الأعلى لحلقة المجموعات الجزئية.

للتحقق مما إذا كان العنصر i موجودًا في المجموعة الجزئية، اختبر البت الخاص به باستخدام mask و1 مزاحة إلى اليسار بمقدار i. وتعني النتيجة غير الصفرية أنه مُضمَّن.

مرّر على كل موضع بت، واجمع العناصر التي يكون بتها مضبوطًا. وهكذا تحوّل mask واحدًا إلى المجموعة الجزئية الفعلية التي يمثّلها.

تمثّل القيمة mask 0 المجموعة الجزئية الفارغة، بينما يمثّل mask المكوّن من جميع الواحدات المجموعة الكاملة. وتحصل على كلتيهما تلقائيًا لأن حلقتك تغطي كل قيمة.

داخل الحلقة، اجمع العناصر المختارة لتقييم كل مجموعة جزئية. وهذا هو جوهر كثير من حلول القوة الغاشمة الصغيرة.

يساوي عدد العناصر المختارة قيمة popcount في mask. وفي Python، تعطيك ‎bin(mask).count('1')‎ النتيجة فورًا.

بما أن عدد المجموعات الجزئية هو 2^n، فإن هذه التقنية تناسب قيمًا صغيرة من n فقط. وتُعدّ قيمة n تساوي 20 تقريبًا الحد العملي للتعداد الكامل.

تستبدل حلقة واحدة من الأعداد حلقات متداخلة معقدة، كما أن عمليات البتات سريعة. فيبقى الكود قصيرًا وواضحًا وسهل الاختبار.

كرّر على mask، وفكّ ترميز بتاته، وقيّم المجموعة الجزئية، واحتفظ بالأفضل. احفظ هذا القالب، وستصبح كثير من مسائل المجموعات الجزئية روتينية.

تريد اختبار ما إذا كان العنصر i مُضمّنًا في المجموعة الجزئية التي يرمّز إليها mask.

كرّر على mask من 0 إلى 2^n ناقص 1، واقرأ البتات باستخدام mask و1 مزاحة إلى اليسار، ثم قيّم كل مجموعة جزئية. إنها طريقة قوة غاشمة واضحة للقيم الصغيرة من n. 🚀