Bitmask Subset Enumeration

n वस्तुओं का प्रत्येक उपसमुच्चय एक ही पूर्णांक से जुड़ता है। 0 से ऊपर तक गिनें, और प्रत्येक संख्या के बिट ठीक यह चुनते हैं कि कौन-सी वस्तुएँ शामिल हैं। 🙂

n तत्वों वाले समुच्चय के 2^n उपसमुच्चय होते हैं। इसलिए किसी पूर्णांक को 0 से 2^n माइनस 1 तक लूप करने पर हर उपसमुच्चय ठीक एक बार देखा जाता है।

1 << n का शिफ्ट 2 की घात n के बराबर होता है। अपने उपसमुच्चय वाले लूप की ऊपरी सीमा लिखने का यह साफ़ और तेज़ तरीका है।

यह जानने के लिए कि आइटम i उपसमुच्चय में है या नहीं, उसके बिट को i स्थान बाईं ओर खिसकाए गए 1 वाले मास्क से जाँचें। शून्येतर परिणाम का अर्थ है कि वह शामिल है।

हर बिट स्थान पर जाएँ और उन तत्वों को इकट्ठा करें जिनका बिट सेट है। इस तरह एक मास्क से उसके द्वारा दर्शाया गया वास्तविक उपसमुच्चय मिल जाता है।

मास्क 0 रिक्त उपसमुच्चय है, और सभी 1 वाला मास्क पूर्ण समुच्चय है। आपका लूप हर मान को कवर करता है, इसलिए दोनों अपने-आप शामिल हो जाते हैं।

लूप के भीतर चुने गए तत्वों को जोड़कर हर उपसमुच्चय का मान निकालें। यह कई छोटे पूर्ण-खोज समाधानों का मूल है।

चुने गए तत्वों की संख्या मास्क में मौजूद 1-बिटों की संख्या के बराबर होती है। पाइथन में, bin(mask).count('1') इसे तुरंत दे देता है।

चूँकि 2^n उपसमुच्चय होते हैं, यह तकनीक केवल छोटे n के लिए उपयुक्त है। पूर्ण गणना के लिए लगभग n = 20 व्यावहारिक ऊपरी सीमा है।

एक पूर्णांक वाला लूप उलझे हुए नेस्टेड लूपों की जगह लेता है, और बिट संचालन तेज़ होते हैं। कोड छोटा, स्पष्ट और परीक्षण करने में आसान रहता है।

मास्क पर लूप चलाएँ, उसके बिट पढ़ें, उपसमुच्चय का मान निकालें और सबसे अच्छे परिणाम को सहेजें। इस रूपरेखा को याद कर लें, तो कई उपसमुच्चय वाली समस्याएँ आसान हो जाती हैं।

मास्क को 0 से 2^n माइनस 1 तक लूप करें, मास्क और बाईं ओर खिसकाए गए 1 से बिट पढ़ें, और हर उपसमुच्चय का मान निकालें। छोटे n के लिए यह साफ़-सुथरी पूर्ण खोज है। 🚀