Phương Pháp Sinh Dãy Nhị Phân Độ Dài N

Kỹ thuật sinh dãy nhị phân độ dài n là một chủ đề cơ bản trong lập trình tổ hợp và thường được dùng để duyệt qua tất cả các khả năng có thể của dãy gồm các ký tự 0 và 1. Dưới đây là phần trình bày chi tiết:

1. Mô tả bài toán cơ sở

Yêu cầu:
Sinh tất cả các dãy nhị phân có độ dài $n$, mỗi dãy gồm các ký tự 0 hoặc 1.

Ví dụ:
Với $n = 3$, ta có 8 dãy nhị phân tương ứng:

000
001
010
011
100
101
110
111

2. Các phương pháp sinh dãy nhị phân

Phương pháp 1: Duyệt toàn bộ bằng đệ quy (Backtracking)

Ý tưởng:

• Tại mỗi vị trí trong dãy, ta chọn 0 hoặc 1.
• Khi đã chọn đủ $n$ phần tử, in ra kết quả.

Code C++ :

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> a;

void Try(int i) {
    if (i == n) {
        for (int x : a) cout << x;
        cout << "\n";
        return;
    }
    for (int bit = 0; bit <= 1; bit++) {
        a[i] = bit;
        Try(i + 1);
    }
}

int main() {
    cin >> n;
    a.resize(n);
    Try(0);
    return 0;
}

Phân tích:

• Số dãy sinh ra: $2^n$
• Độ phức tạp: $O(2^n * n)$

Phương pháp 2: Sinh theo thứ tự từ điển (Iterative)

Ý tưởng:

• Bắt đầu từ dãy gồm N phần tử toàn 0.
• Mỗi lần, tìm bit 0 phải nhất → đổi nó thành 1 → đổi tất cả bit bên phải nó thành 0.

Code C++:

#include <bits/stdc++.h>
using namespace std;

void sinh(int n) {
    vector<int> a(n, 0);
    while (true) {
        for (int x : a) cout << x;
        cout << "\n";

        int i = n - 1;
        while (i >= 0 && a[i] == 1) i--;
        if (i < 0) break; // kết thúc
        a[i] = 1;
        for (int j = i + 1; j < n; j++) a[j] = 0;
    }
}

int main() {
    int n;
    cin >> n;
    sinh(n);
    return 0;
}

Phương pháp 3: Sử dụng biểu diễn nhị phân của số tự nhiên

Ý tưởng:

• Duyệt các số từ $0 → 2^n - 1$.
• In ra dạng nhị phân có độ dài đúng n.

Code C++ ngắn gọn:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < (1 << n); i++) {
        string s = "";
        for (int j = n - 1; j >= 0; j--)
            s += ((i >> j) & 1) + '0';
        cout << s << "\n";
    }
}

3. So sánh các phương pháp

Phương pháp	Ý tưởng chính	Ưu điểm	Nhược điểm
Đệ quy (Try)	Sinh nhánh theo chiều sâu	Dễ hiểu, dễ mở rộng (áp dụng cho hoán vị, tổ hợp)	Dùng ngăn xếp đệ quy, tốn bộ nhớ khi n lớn
Lặp (Iterative)	Tăng dần theo từ điển	Không cần đệ quy, sinh nhanh	Khó mở rộng cho bài phức tạp
Duyệt số nguyên	Dùng bitmask	Cực ngắn gọn, hiệu quả cao	Khó hiểu với người mới bắt đầu

4. Ứng dụng

• Duyệt tất cả các tập con của một tập $n$ phần tử.
• Sinh dữ liệu kiểm thử trong bài toán tổ hợp.
• Sinh nghiệm trong bài toán tối ưu (ví dụ: bài toán balo nhị phân).
• Là nền tảng cho kỹ thuật Bitmask Dynamic Programming.