Combinatoric

Generating Subsets

มีหลายปัญหาในการเขียนโปรแกรมที่เราจะต้องแก้ด้วยการสร้างซับเซตทั้งหมดที่เป็นไปได้ขึ้นมา เพื่อทดสอบวิธีที่เป็นไปได้ทั้งหมด ปัญหาที่เกิดขึ้นคือจะสร้างซับเซตได้อย่างไร?

ความรู้แรกที่ทุกคนน่าจะมีเกี่ยวกับซับเซตทั้งหมดของเซตหนึ่งๆคือ ซับเซตทั้งหมดจะมี $2^n$ แบบ (เมื่อเซตนั้นมีสมาชิก n ตัว) เช่น เซต {1, 2, 3} มีซับเซตที่เป็นไปได้ทั้งหมด 8 ตัวได้แก่ {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3} และ {1,2,3}

ทีนี้เราจะใช้เลขฐานสองเข้ามาช่วยในการสร้างซับเซตทั้งหมดแล้วครับ ลองดูเลขฐานสองของ 0 จนถึง 7 ดูครับ

Taxonomy upgrade extras: 

Subscribe to RSS - Combinatoric