Chương 5.2 • Enumeration & Bitmask

🧮 Sinh cấu hình và Bitmask Enumeration

Sinh cấu hình là kỹ thuật liệt kê có hệ thống mọi trạng thái hợp lệ. Bitmask biến một tập con thành một số nguyên, nhờ đó thao tác chọn, bỏ chọn, kiểm tra phần tử và duyệt submask trở nên ngắn gọn, hiệu quả.

2ⁿSố tập con

n!Số hoán vị

popcountĐếm bit 1

submaskDuyệt mọi tập con của mask

Mục tiêu Đặt vấn đề Dãy nhị phân Tập con Tổ hợp Hoán vị Phép toán bit Submask Phân tích Code mẫu Giải thích code Lỗi thường gặp Quiz

🎯 Mục tiêu bài học

Cần hiểu

Khái niệm cấu hình và thứ tự sinh.
Sinh dãy nhị phân, tập con, tổ hợp, hoán vị.
Ý nghĩa bit thứ i trong mask.
Các phép bit: AND, OR, XOR, SHIFT.
Duyệt submask và dùng popcount.

Cần làm được

Liệt kê mọi tập con bằng mask.
Lọc tập con có đúng k phần tử.
Dùng next_permutation.
Kiểm tra, bật, tắt, đảo bit.
Duyệt mọi submask của một mask cho trước.

1. Đặt vấn đề

Bài toán mở đầu.
Có n món đồ. Mỗi món có thể được chọn hoặc không chọn. Hãy liệt kê mọi phương án chọn và tìm phương án có tổng giá trị lớn nhất không vượt quá giới hạn W.

1.1. Mỗi món tương ứng một bit

Bit i bằng 1: chọn món i.
Bit i bằng 0: không chọn món i.

mask từ 0 đến 2ⁿ−1 biểu diễn toàn bộ 2ⁿ tập con

1.2. Vì sao cần sinh cấu hình có hệ thống?

Nếu liệt kê thủ công, dễ thiếu hoặc trùng. Thuật toán sinh giúp đi qua mỗi cấu hình đúng một lần, theo thứ tự rõ ràng.

Kết luận: Sinh cấu hình phù hợp khi n nhỏ và cần duyệt toàn bộ không gian trạng thái để kiểm tra, tối ưu hoặc đếm.

2. Sinh dãy nhị phân

Dãy nhị phân độ dài n có 2ⁿ cấu hình, từ 00...0 đến 11...1.

Độ dài n

Nhìn theo số nguyên: tăng mask thêm 1 chính là chuyển sang cấu hình nhị phân tiếp theo.

3. Liệt kê tập con bằng Bitmask

Các phần tử mask

Kiểm tra phần tử i: (mask & (1 << i)) != 0

4. Sinh tổ hợp k phần tử

Tổ hợp chọn đúng k phần tử trong n phần tử có số lượng C(n,k). Có hai cách thông dụng:

Lọc theo popcount

for (int mask = 0; mask < (1 << n); mask++) {
    if (__builtin_popcount(mask) == k) {
        // mask là một tổ hợp k phần tử
    }
}

Quay lui

void generate(int start) {
    if ((int)chosen.size() == k) {
        print();
        return;
    }

    for (int value = start; value <= n; value++) {
        chosen.push_back(value);
        generate(value + 1);
        chosen.pop_back();
    }
}

n k

5. Hoán vị và next_permutation

next_permutation biến dãy thành hoán vị kế tiếp theo thứ tự từ điển. Muốn sinh đủ mọi hoán vị, nên sắp xếp dãy ban đầu.

Dãy

Dữ liệu trùng: next_permutation vẫn sinh các hoán vị phân biệt theo giá trị, không sinh bản sao giống hệt nhau.

6. Các phép toán bit thường dùng

Mục đích	Công thức	Giải thích
Kiểm tra bit i	`mask & (1<`	Khác 0 nếu bit i đang bật.
Bật bit i	`mask \|= (1<`	Đặt bit i thành 1.
Tắt bit i	`mask &= ~(1<`	Đặt bit i thành 0.
Đảo bit i	`mask ^= (1<`	0 thành 1, 1 thành 0.
Đếm bit 1	`__builtin_popcount(mask)`	Dùng cho int.
Bit thấp nhất đang bật	`mask & -mask`	Tách lowest set bit.
Xóa bit thấp nhất đang bật	`mask &= mask-1`	Giảm số bit 1 đi một.

6.1. Mô phỏng thao tác bit

mask bit i

7. Duyệt mọi submask của một mask

for (int sub = mask; ; sub = (sub - 1) & mask)

Mỗi submask chỉ chứa các bit đã bật trong mask ban đầu.

mask

Chú ý sub = 0: Nếu viết vòng while(sub), cần xử lý 0 riêng khi bài yêu cầu tính cả tập rỗng.

8. Phân tích thuật toán

Kỹ thuật	Số cấu hình	Độ phức tạp	Điều kiện sử dụng
Dãy nhị phân độ dài n	2ⁿ	O(2ⁿ·n) nếu in đủ	n nhỏ.
Tập con bằng mask	2ⁿ	O(2ⁿ·n)	Thường n ≤ 20–25 tùy bài.
Tổ hợp k phần tử	C(n,k)	O(C(n,k)·k)	Quay lui hiệu quả hơn lọc khi k nhỏ.
Hoán vị	n!	O(n!·n)	n rất nhỏ.
Duyệt submask của mask	2^popcount(mask)	O(2^k)	k là số bit 1.
Duyệt mọi mask và mọi submask	3ⁿ	O(3ⁿ)	Mỗi bit: ngoài, trong submask, hoặc trong mask nhưng không trong submask.

Không gian trạng thái tăng rất nhanh. Trước khi sinh, luôn ước lượng 2ⁿ, C(n,k), n! hoặc 3ⁿ.

9. Code mẫu

#include 
using namespace std;

int main() {
    int n;
    cin >> n;

    for (int mask = 0;
         mask < (1 << n);
         mask++) {
        for (int bit = n - 1;
             bit >= 0;
             bit--) {
            cout << ((mask >> bit) & 1);
        }

        cout << '
';
    }
}

#include 
using namespace std;

int main() {
    vector a = {10, 20, 30};
    int n = a.size();

    for (int mask = 0;
         mask < (1 << n);
         mask++) {
        cout << "{ ";

        for (int bit = 0; bit < n; bit++) {
            if (mask & (1 << bit)) {
                cout << a[bit] << ' ';
            }
        }

        cout << "}
";
    }
}

#include 
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    for (int mask = 0;
         mask < (1 << n);
         mask++) {
        if (__builtin_popcount(
                (unsigned)mask
            ) != k) {
            continue;
        }

        for (int bit = 0; bit < n; bit++) {
            if (mask & (1 << bit)) {
                cout << bit + 1 << ' ';
            }
        }

        cout << '
';
    }
}

#include 
using namespace std;

int main() {
    vector a = {1, 2, 3};

    sort(a.begin(), a.end());

    do {
        for (int value : a) {
            cout << value << ' ';
        }
        cout << '
';
    } while (
        next_permutation(
            a.begin(),
            a.end()
        )
    );
}

#include 
using namespace std;

int main() {
    int mask;
    cin >> mask;

    int sub = mask;

    while (true) {
        cout << sub << '
';

        if (sub == 0) {
            break;
        }

        sub = (sub - 1) & mask;
    }
}

items = ["A", "B", "C"]
n = len(items)

for mask in range(1 << n):
    subset = []

    for bit in range(n):
        if mask & (1 << bit):
            subset.append(items[bit])

    print(subset)

mask = 13
sub = mask

while True:
    print(sub)

    if sub == 0:
        break

    sub = (sub - 1) & mask

10. Giải thích code

10.1. Vì sao có 1<
`1< bằng 2ⁿ. Mỗi mask từ 0 đến 2ⁿ−1 tương ứng đúng một dãy n bit.`
10.2. Vì sao dùng mask & (1< 1< tạo số chỉ có bit i bằng 1. Phép AND giữ lại bit đó nếu mask đang bật bit i. 10.3. next_permutation trả về gì? Trả về true nếu còn hoán vị kế tiếp; khi đang ở hoán vị lớn nhất, hàm đưa dãy về nhỏ nhất và trả về false. 10.4. Vì sao sub=(sub−1)&mask duyệt đúng submask? sub-1 chuyển sang mẫu bit nhỏ hơn; AND với mask loại bỏ mọi bit không thuộc mask gốc. 10.5. __builtin_popcountll dùng khi nào? Dùng cho số 64-bit. Với unsigned long long, ưu tiên __builtin_popcountll. 10.6. Vì sao duyệt mọi mask và mọi submask là O(3ⁿ)? Mỗi bit có ba trạng thái: không thuộc mask, thuộc mask nhưng không thuộc submask, hoặc thuộc cả hai.




  11. Lỗi thường gặp

  
    Dùng 1< khi n quá lớn cho int.

    Nhầm thứ tự bit và thứ tự phần tử.
    Quên ngoặc trong mask & (1<.

    Sinh hoán vị nhưng không sắp xếp dãy ban đầu.
    Duyệt submask nhưng bỏ sót sub = 0.
    Dùng popcount int cho mask 64-bit.
    Không ước lượng 2ⁿ, n! hoặc 3ⁿ trước khi chạy.
    Nhầm tổ hợp với hoán vị.
    Dùng bitmask khi n vượt số bit của kiểu dữ liệu.
  




  12. Quiz và bài tập

  Câu 1. Tập n phần tử có bao nhiêu tập con?


  Câu 2. Công thức kiểm tra bit i đang bật?


  Câu 3. Hàm sinh hoán vị kế tiếp trong STL?


  Câu 4. Duyệt mọi mask và mọi submask có độ phức tạp tổng quát nào?


  
    📘 Cơ bản
In mọi dãy nhị phân độ dài n.
Liệt kê mọi tập con.
Đếm bit 1 của mask.
    📗 Trung bình
Sinh tổ hợp k phần tử.
Sinh mọi hoán vị.
Tìm tập con có tổng lớn nhất ≤ W.
    📙 Nâng cao
Duyệt mọi submask.
Đếm cặp tập con rời nhau.
DP Bitmask cơ bản.
    🐉 HSG
Meet-in-the-middle.
Sum over Subsets DP.
Held–Karp TSP.