โปรแกรม C พิมพ์ทุก subset ของ {1,2,3,...n} โดยไม่ใช้ Array หรือ Loop (Recursion)

ได้รับจำนวนเต็มบวก n ภารกิจคือพิมพ์ทุก subset ของเซต {1, 2, 3, ..., n} โดยไม่ใช้ array หรือ loop ใช้ recursion เท่านั้น

เช่น n=3 เซตคือ {1,2,3} subset ทั้งหมด: {1 2 3}, {1 2}, {2 3}, {1 3}, {1}, {2}, {3}, {}

ตัวอย่าง

Input: 3
Output: { 1 2 3 }{ 1 2 }{ 1 3 }{ 1 }{ 2 3 }{ 2 }{ 3 }{ }

Input: 4
Output: { 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }

แนวทาง (ใช้ Binary Representation)

• เริ่มจาก num = 2ⁿ - 1 ลงมาจนถึง 0
• แปลง num เป็น binary n บิต
• บิตที่ 1 (MSB) แทน 1, บิตที่ 2 แทน 2, ..., บิตที่ n แทน n
• พิมพ์ตัวเลขที่บิตเป็น 1
• ทำซ้ำสำหรับทุกค่า num

ตัวอย่าง n=3: num เริ่มที่ 7 (111) → {1 2 3}, 6 (110) → {1 2}, 5 (101) → {1 3}, 4 (100) → {1}, 3 (011) → {2 3}, 2 (010) → {2}, 1 (001) → {3}, 0 (000) → {}

อัลกอริทึม

Start
Step 1: subset(bitn, num, num_of_bits)
    ถ้า bitn >= 0:
        ถ้า (num & (1 << bitn)) != 0 พิมพ์ num_of_bits - bitn
        เรียก subset(bitn-1, num, num_of_bits)
    ไม่เช่นนั้น return 0
    return 1

Step 2: printSubSets(num_of_bits, num)
    ถ้า num >= 0:
        พิมพ์ "{ "
        เรียก subset(num_of_bits-1, num, num_of_bits)
        พิมพ์ "}"
        เรียก printSubSets(num_of_bits, num-1)
    ไม่เช่นนั้น return 0
    return 1

Step 3: main() n=4 เรียก printSubSets(n, 2^n - 1)
Stop

โค้ดตัวอย่าง

#include <stdio.h>
#include <math.h>

int subset(int bitn, int num, int num_of_bits) {
    if (bitn >= 0) {
        if ((num & (1 << bitn)) != 0)
            printf("%d ", num_of_bits - bitn);
        subset(bitn - 1, num, num_of_bits);
    } else return 0;
    return 1;
}

int printSubSets(int num_of_bits, int num) {
    if (num >= 0) {
        printf("{ ");
        subset(num_of_bits - 1, num, num_of_bits);
        printf("}");
        printSubSets(num_of_bits, num - 1);
    } else return 0;
    return 1;
}

int main() {
    int n = 4;
    printSubSets(n, (int)(pow(2, n)) - 1);
}

ผลลัพธ์

{ 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }