แจกแจงเซตย่อยด้วยบิตมาสก์

เซตย่อยทุกเซตของสิ่งของ n ชิ้นสามารถจับคู่กับจำนวนเต็มเพียงหนึ่งจำนวน นับจาก 0 ขึ้นไป แล้วบิตของแต่ละจำนวนจะเลือกว่าสิ่งของตัวใดอยู่ในเซตย่อย 🙂

เซตที่มีสมาชิกจำนวน n รายการมีสับเซต 2^n ชุด ดังนั้นการวนค่าจำนวนเต็มตั้งแต่ 0 ถึง 2^n ลบ 1 จะเยี่ยมชมสับเซตแต่ละชุดครบหนึ่งครั้งพอดี

การเลื่อน 1 << n มีค่าเท่ากับ 2 ยกกำลัง n จึงเป็นวิธีเขียนขอบเขตบนของลูปสับเซตที่กระชับและรวดเร็ว

หากต้องการตรวจว่าสมาชิก i อยู่ในสับเซตหรือไม่ ให้ตรวจสอบ บิต ของสมาชิกนั้นด้วยมาสก์และ 1 ที่เลื่อนไปทางซ้าย i ตำแหน่ง ผลลัพธ์ที่ไม่ใช่ศูนย์หมายความว่าสมาชิกนั้นถูกรวมอยู่ด้วย

ตรวจดูแต่ละตำแหน่งบิต แล้วรวบรวมสมาชิกที่มี บิต เป็น 1 วิธีนี้จะแปลงมาสก์หนึ่งค่าให้เป็นสับเซตจริงที่มาสก์นั้นแทนอยู่

มาสก์ 0 คือสับเซตว่าง ส่วนมาสก์ที่มีบิตเป็น 1 ทั้งหมดคือเซตเต็ม ทั้งสองกรณีเกิดขึ้นได้โดยอัตโนมัติ เพราะลูปของคุณครอบคลุมค่าทุกค่า

ภายในลูป ให้นำสมาชิกที่เลือกมาบวกกันเพื่อให้คะแนนแต่ละสับเซต นี่คือหัวใจของวิธีแก้ปัญหาแบบ ลองทุกกรณี ขนาดเล็กจำนวนมาก

จำนวนสมาชิกที่เลือกจะเท่ากับจำนวนบิตที่เป็น 1 ของมาสก์ ใน Python, bin(mask).count('1') จะให้ค่านี้ได้ทันที

เนื่องจากมีสับเซตจำนวน 2^n ชุด เทคนิคนี้จึงเหมาะกับค่า n ขนาดเล็กเท่านั้น โดยทั่วไป n ประมาณ 20 ถือเป็นขีดสูงสุดที่ใช้งานได้จริงสำหรับการไล่ตรวจทุกกรณี

ลูปจำนวนเต็มเพียงลูปเดียวใช้แทนลูปซ้อนที่ยุ่งยากได้ และการดำเนินการระดับบิตก็ รวดเร็ว โค้ดจึงสั้น ชัดเจน และทดสอบได้ง่าย

วนลูปผ่าน มาสก์ ถอดรหัสบิตของมัน ให้คะแนนสับเซต แล้วเก็บคำตอบที่ดีที่สุด จดจำโครงแบบนี้ไว้ แล้วปัญหาเกี่ยวกับสับเซตจำนวนมากจะกลายเป็นงานที่ทำได้เป็นขั้นตอน

คุณต้องการตรวจว่าสมาชิก i ถูกรวมอยู่ในสับเซตที่เข้ารหัสด้วยมาสก์หรือไม่

วน มาสก์ ตั้งแต่ 0 ถึง 2^n ลบ 1 อ่านบิตด้วยมาสก์และ 1 ที่เลื่อนไปทางซ้าย แล้วให้คะแนนแต่ละสับเซต นี่คือวิธีลองทุกกรณีที่กระชับสำหรับค่า n ขนาดเล็ก 🚀