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

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

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

0 - 000
1 - 001
2 - 010
3 - 011
4 - 100
5 - 101
6 - 110
7 - 111

สังเกตเห็นอะไรมั้ยครับ ถ้าเรามองแต่ละหลักของเลขฐานสองเป็นการเลือกหรือไม่เลือกสมาชิกของเซต โดยให้เลข 1 หมายถึงเลือก และ 0 หมายถึงไม่เลือก เราจะได้ซับเซตที่เป็นไปได้ทั้งหมดของเซตที่มีขนาด 3 ตัว เช่น

000 จะเป็น $\{\}$ - หมายถึงไม่เลือกสมาชิกตัวใดเลย
011 จะเป็น $\{2,3\}$ - หมายถึงเลือกสมาชิกตัวที่สองและสามมาสร้างเป็นเซตใหม่
010 จะเป็น $\{1\}$ - หมายถึงเลือกเฉพาะสมาชิกตัวแรกมาสร้างเป็นเซตใหม่

โอ้! มหัศจรรย์มาก ถึงตรงนี้เรารู้แล้วครับ ว่าถ้ามีเซตขนาด n เราสามารถใช้เลขฐานสองของ $0$ ถึง $2^n - 1$ เข้ามาช่วยได้ ซึ่งจริงๆแล้วเราสามารถแปลงเลขฐานสิบเป็นเลขฐานสองได้ง่ายมากครับ ถ้าเราใช้ bit ที่ represent ตัวเลขฐานสิบตัวนั้น ลองดูตัวอย่างโปรแกรมกันเลยครับ

void generate_subset(int n) {
    int *sequence = new int[n];
    int subset_num = pow(2, n);
    for (int i = 0; i < subset_num; i++) { 
        extract_bit(i, sequence, n);
        print_sequence(sequence, n);
    }

    delete sequence;
}

ฟังก์ชัน generate_subset เป็นฟังก์ชันที่รับขนาดของเซต และพิมพ์ซับเซตที่เป็นไปได้ทั้งหมดออกมา (โดยในที่นี้จะไม่รับเซตเข้ามานะครับ รับแต่ขนาดแล้วจะพิมพ์ออกมาเป็น 0,1 เพื่อบอกว่าจะเลือกตัวไหนบ้าง เหมือนตัวอย่างด้านบน) เริ่มต้นฟังก์ชันก็จะสร้างอาร์เรย์ขนาดเท่ากับขนาดของเซต ตัวนี้จะเอาไปเก็บค่า 0,1 ของแต่ละซับเซตครับ จากนั้นก็วนลูปตั้งแต่ $0$ ถึง $2^n - 1$ ตามที่บอกไว้ก่อนหน้านี้

จากนั้นฟังก์ชัน extract_bit จะนำค่าเลขจำนวนเต็มเข้าไป แล้วแปลงเป็นฐานสองออกมาเพื่อเก็บไว้ในอาร์เรย์ครับ อย่างเช่น ถ้าอาร์เรย์ sequence มีขนาด 3 และ i มีค่าเป็น 5 ฟังก์ชันนี้จะแกะแต่ละบิต (ซึ่งก็คือเลขฐานสอง) มาเก็บไวในอาร์เรย์เป็น [1,0,1]

void extract_bit(int n, int *array, int size) {
	for (int i = size-1; i >= 0; --i) {
		array[i] = (n & 0x01);
		n = n >> 1;
	}
}

ฟังก์ชัน extract_bit จะแกะค่าของแต่ละบิตมาเก็บไว้ในอาร์เรย์ได้อย่างไร คำตอบคือเราจะใช้ bit operator &(and) และ >>(shift right) ครับ คอนเซ็ปต์ของการ bit and คือ บิตที่เป็น 1 เหมือนกันจะกลายเป็น 1 นอกนั้นจะเป็น 0 ทำให้ถ้าเราเอาเลขตัวนั้นไป bit and กับ 0x01 (ซึ่งในฐานสองจะเป็น 00000001) จะได้บิตสุดท้ายของเลขตัวนั้นมาครับว่าเป็น 1 หรือ 0

ทีนี้จะหาค่าสองบิตตัวถัดไปได้ยังไงล่ะ? คราวนี้เราจะใช้การ shift right(>>) ครับ เลื่อนบิตถัดไปมาเป็นบิตสุดท้ายแทน เช่น 00110010 เมื่อ shift right จะเป็น 00011001 และถ้า shift right อีกทีก็จะเป็น 00001100 เราก็ทำการวนเท่ากับขนาดของจำนวนอาร์เรย์แล้วก็เก็บค่า 0,1 เข้าไปเรื่อยๆครับ

void print_sequence(int *seq, int size) {
    std::cout << "{"; 
    for (int i = 0; i < size; ++i) { 
        if (i != 0) std::cout << ","; 
        std::cout << seq[i]; 
    } 
    std::cout << "}\n";
}

ฟังก์ชันนี้มีไว้พิมพ์ออกมาให้ดูสวยๆเท่านั้นเองครับ ไม่มีสารถแก่นสารใดๆทั้งสิ้น

ทีนี้ถ้าลองเรียกโปรแกรมนี้ด้วยขนาดเท่ากับ 4 -- generate_subset(4); ก็จะได้ออกมาเป็น

{0,0,0,0}   {0,0,0,1}   {0,0,1,0}   {0,0,1,1}
{0,1,0,0}   {0,1,0,1}   {0,1,1,0}   {0,1,1,1}
{1,0,0,0}   {1,0,0,1}   {1,0,1,0}   {1,0,1,1}
{1,1,0,0}   {1,1,0,1}   {1,1,1,0}   {1,1,1,1}

ทดลองให้ดูด้วยตัวเลขน้อยๆนะครับ ถ้าเยอะกว่านี้ก็คงจะออกมาบานเบอะ

ปล. ผมเข้าใจเอาเองนะว่าคนส่วนใหญ่จะไม่ค่อยได้ใช้พวก bit operator เท่าไหร่ แต่จริงๆแล้วมันเอาไปทำอะไรเท่ๆได้เยอะมากเลยครับ ลองไปเล่นกันดูครับ