Thuật toán sinh kế tiếp: sinh nhị phân, tổ hợp, hoán vị (next_permutation) C++ và Python

Khung tư duy chung của Thuật toán sinh kế tiếp

Bên cạnh cách dùng đệ quy và quay lui, bạn còn có một công cụ duyệt tổ hợp rất gọn gàng là thuật toán sinh kế tiếp (Iterative Generation).

Hai điều kiện để áp dụng thuật toán sinh kế tiếp là:

1. Xác định được thứ tự từ điển (lexicographical order) giữa các cấu hình, từ đó biết rõ cấu hình đầu tiên (nhỏ nhất) và cấu hình cuối cùng (lớn nhất).
2. Xây dựng được quy tắc biến đổi từ cấu hình hiện tại sang cấu hình kế tiếp ngay sau nó (lớn hơn nó nhưng nhỏ nhất có thể).

Nguyên lý chung ở cả 3 bài toán dưới đây luôn là: để cấu hình mới chỉ lớn hơn cấu hình cũ một lượng nhỏ nhất, ta phải giữ nguyên phần tiền tố bên trái càng dài càng tốt. Vì vậy, ta luôn dò từ phải sang trái (từ cuối mảng ngược về đầu) để tìm vị trí đầu tiên còn tăng được, tăng nhẹ vị trí đó lên một nấc, rồi đặt toàn bộ phần đuôi bên phải nó về trạng thái nhỏ nhất!

Quy tắc 1: Sinh xâu nhị phân độ dài n

Bài toán yêu cầu liệt kê tất cả 2n xâu nhị phân độ dài n theo thứ tự từ 00...0 đến 11...1 (ví dụ n = 3: 000, 001, 010, 011, 100, 101, 110, 111).

Việc chuyển sang xâu nhị phân kế tiếp giống hệt phép cộng thêm 1 ở hệ nhị phân (xem thêm bài phép toán bit):

• Cấu hình đầu tiên: Xâu toàn '0' ("00...0"). Cấu hình cuối cùng: Xâu toàn '1' ("11...1").
• Quy tắc sinh kế tiếp:
  1. Duyệt chỉ số i từ cuối xâu (n - 1) ngược về 0.
  2. Chừng nào gặp s[i] == '1' thì đổi thành '0' (do 1 + 1 = 0 nhớ 1 sang trái) và lùi i--.
  3. Nếu i < 0 (cả xâu vốn toàn '1'), thuật toán dừng. Ngược lại, s[i] là chữ số '0' đầu tiên tính từ phải sang: đổi s[i] = '1' là xong!

Quy tắc 2: Sinh tổ hợp chập k của n phần tử

Cho tập hợp {1, 2, ..., n}. Để mỗi tập con k phần tử chỉ xuất hiện một lần theo thứ tự từ điển, ta biểu diễn tổ hợp bằng mảng c gồm k phần tử tăng dần nghiêm ngặt: \[1 \le c[0] < c[1] < \dots < c[k - 1] \le n\]

Xét giá trị tối đa mà phần tử tại chỉ số i (0 ≤ i < k) có thể nhận: phần tử cuối c[k - 1] tối đa bằng n; phần tử kế cuối c[k - 2] tối đa bằng n - 1; tổng quát, vị trí i phải chừa chỗ cho (k - 1) - i số lớn hơn đứng sau, nên giới hạn tối đa tại vị trí i là n - k + i + 1.

Quy tắc sinh tổ hợp kế tiếp (ví dụ n = 4, k = 3: [1, 2, 3] → [1, 2, 4] → [1, 3, 4] → [2, 3, 4]):

• Cấu hình đầu: c = [1, 2, ..., k]. Cấu hình cuối: c = [n - k + 1, ..., n].
• Quy tắc biến đổi:
  1. Dò i từ k - 1 ngược về 0 tìm vị trí đầu tiên chưa chạm trần: c[i] < n - k + i + 1 (tức n - k + i + 1 > c[i]). Nếu i < 0 thì dừng.
  2. Tăng vị trí đó lên 1: c[i]++.
  3. Đặt các phần tử bên phải i (j = i + 1 .. k - 1) tăng dần liên tiếp: c[j] = c[j - 1] + 1.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 1. Sinh xâu nhị phân kế tiếp (trả về false nếu đã ở cấu hình cuối 11...1)
bool sinhNhiPhanKeTiep(string& s) {
    int i = (int)s.size() - 1;
    while (i >= 0 && s[i] == '1') {
        s[i] = '0';  // đổi các bit 1 ở cuối thành 0
        i--;
    }
    if (i < 0) return false;  // đã đạt cấu hình cuối cùng toàn bit 1
    s[i] = '1';               // bật bit 0 đầu tiên từ phải sang thành 1
    return true;
}

// 2. Sinh tổ hợp chập k của n kế tiếp (mảng c đánh chỉ số 0 .. k-1, giá trị từ 1 .. n)
bool sinhToHopKeTiep(vector<int>& c, int n) {
    int k = (int)c.size();
    int i = k - 1;
    // Giá trị tối đa tại vị trí i (0-indexed) là n - k + i + 1
    while (i >= 0 && c[i] == n - k + i + 1) {
        i--;
    }
    if (i < 0) return false;  // đã đạt cấu hình cuối [n-k+1 .. n]
    c[i]++;
    for (int j = i + 1; j < k; j++) {
        c[j] = c[j - 1] + 1;
    }
    return true;
}

int main() {
    string s = "000";
    do {
        cout << s << " ";
    } while (sinhNhiPhanKeTiep(s));
    cout << "\n";  // 000 001 010 011 100 101 110 111

    vector<int> c = {1, 2, 3};
    int n = 4;
    do {
        cout << c[0] << c[1] << c[2] << " ";
    } while (sinhToHopKeTiep(c, n));
    cout << "\n";  // 123 124 134 234
    return 0;
}

def sinh_nhi_phan_ke_tiep(s):
    """Sinh xâu nhị phân kế tiếp từ danh sách ký tự s, trả về True nếu còn cấu hình kế tiếp."""
    i = len(s) - 1
    while i >= 0 and s[i] == "1":
        s[i] = "0"
        i -= 1
    if i < 0:
        return False
    s[i] = "1"
    return True


def sinh_to_hop_ke_tiep(c, n):
    """Sinh tổ hợp chập k của n kế tiếp (c lưu các số từ 1..n tăng dần)."""
    k = len(c)
    i = k - 1
    while i >= 0 and c[i] == n - k + i + 1:
        i -= 1
    if i < 0:
        return False
    c[i] += 1
    for j in range(i + 1, k):
        c[j] = c[j - 1] + 1
    return True


s = list("000")
nhi_phan = []
while True:
    nhi_phan.append("".join(s))
    if not sinh_nhi_phan_ke_tiep(s):
        break
print(*nhi_phan)  # 000 001 010 011 100 101 110 111

c = [1, 2, 3]
to_hop = []
while True:
    to_hop.append("".join(map(str, c)))
    if not sinh_to_hop_ke_tiep(c, 4):
        break
print(*to_hop)    # 123 124 134 234

Quy tắc 3: Sinh hoán vị kế tiếp (Next Permutation)

Đây là thuật toán cốt lõi bên trong hàm std::next_permutation của C++ và bài phỏng vấn kinh điển Next Permutation.

Xét hoán vị a = [1, 3, 5, 4, 2]. Nhìn vào đoạn đuôi [5, 4, 2]: vì 3 số này đã xếp giảm dần, không thể đổi chỗ nội bộ trong [5, 4, 2] để tạo ra cấu hình lớn hơn nữa. Muốn tăng cấu hình, ta phải mở rộng sang trái tới a[1] = 3 (vị trí đầu tiên từ phải sang có a[i] < a[i + 1], gọi là điểm gãy).

Quy tắc 3 bước tìm hoán vị kế tiếp của a[0 .. n - 1]:

1. Bước 1 (Tìm điểm gãy i): Dò i từ n - 2 ngược về 0, dừng ở vị trí đầu tiên có a[i] < a[i + 1] (a[i + 1] > a[i]). Nếu i < 0 (cả mảng đã giảm dần), đây là hoán vị cuối cùng.
2. Bước 2 (Đổi chỗ với a[j]): Trong đoạn đuôi giảm dần a[i + 1 .. n - 1], dò j từ n - 1 ngược về i + 1 để tìm phần tử đầu tiên thỏa a[j] > a[i] (số nhỏ nhất ở đuôi nhưng lớn hơn a[i]), rồi đổi chỗ swap(a[i], a[j]).
3. Bước 3 (Lật ngược đoạn đuôi): Sau khi đổi chỗ, đoạn đuôi a[i + 1 .. n - 1] vẫn đang giảm dần. Ta lật ngược (reverse) đoạn a[i + 1 .. n - 1] để đưa nó về thứ tự tăng dần nhỏ nhất!

Hàm thư viện: std::next_permutation (C++) và itertools (Python)

Khi giải bài, bạn có thể gọi thẳng thư viện chuẩn:

• Trong C++ (<algorithm>): next_permutation(a.begin(), a.end()) biến đổi vector a sang hoán vị kế tiếp và tự xử lý đúng cả khi mảng có phần tử trùng nhau.
• Trong Python (itertools): Dùng itertools.product([0, 1], repeat=n) cho xâu nhị phân, itertools.combinations(a, k) cho tổ hợp và itertools.permutations(a) cho hoán vị. Thứ tự theo vị trí trong đầu vào; muốn thứ tự từ điển theo giá trị thì sắp xếp đầu vào trước. permutations([1, 1, 2]) vẫn sinh bản trùng vì coi hai vị trí chứa 1 là khác nhau, khác với next_permutation.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Tự cài đặt hàm sinh hoán vị kế tiếp (tương đương std::next_permutation)
bool hoanViKeTiep(vector<int>& a) {
    int n = (int)a.size();
    // Bước 1: Tìm điểm gãy đầu tiên từ phải sang sao cho a[i] < a[i + 1]
    int i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) {
        i--;
    }
    if (i < 0) return false;  // mảng đã giảm dần hoàn toàn (cấu hình cuối)

    // Bước 2: Tìm từ phải sang phần tử a[j] đầu tiên lớn hơn a[i] rồi đổi chỗ
    int j = n - 1;
    while (a[j] <= a[i]) {
        j--;
    }
    swap(a[i], a[j]);

    // Bước 3: Lật ngược đoạn đuôi từ i + 1 đến n - 1 thành tăng dần
    reverse(a.begin() + i + 1, a.end());
    return true;
}

int main() {
    // Ví dụ minh họa tìm hoán vị kế tiếp của [1, 3, 5, 4, 2]
    vector<int> v = {1, 3, 5, 4, 2};
    hoanViKeTiep(v);
    for (size_t i = 0; i < v.size(); i++) {
        cout << v[i] << (i + 1 == v.size() ? "\n" : " ");
    }  // 1 4 2 3 5

    // Dùng std::next_permutation có sẵn để duyệt mọi hoán vị của [1, 2, 3]
    vector<int> p = {1, 2, 3};
    do {
        cout << p[0] << p[1] << p[2] << " ";
    } while (next_permutation(p.begin(), p.end()));
    cout << "\n";  // 123 132 213 231 312 321
    return 0;
}

import itertools


def hoan_vi_ke_tiep(a):
    """Tự cài đặt thuật toán sinh hoán vị kế tiếp tại chỗ (next_permutation)."""
    n = len(a)
    # Bước 1: Tìm điểm gãy đầu tiên từ phải sang sao cho a[i] < a[i + 1]
    i = n - 2
    while i >= 0 and a[i] >= a[i + 1]:
        i -= 1
    if i < 0:
        return False

    # Bước 2: Tìm từ phải sang phần tử a[j] đầu tiên lớn hơn a[i] rồi đổi chỗ
    j = n - 1
    while a[j] <= a[i]:
        j -= 1
    a[i], a[j] = a[j], a[i]

    # Bước 3: Lật ngược đoạn đuôi từ i + 1 đến hết
    a[i + 1 :] = reversed(a[i + 1 :])
    return True


v = [1, 3, 5, 4, 2]
hoan_vi_ke_tiep(v)
print(*v)  # 1 4 2 3 5

# Dùng itertools.permutations trong thư viện chuẩn của Python
all_p = ["".join(map(str, p)) for p in itertools.permutations([1, 2, 3])]
print(*all_p)  # 123 132 213 231 312 321

Chi phí liệt kê và các trường hợp biên

Một bước sinh nhị phân hay hoán vị có cận O(n); sinh tổ hợp có cận O(k). Nếu xuất đầy đủ từng cấu hình thì riêng đầu ra đã cần Θ(n·2ⁿ), Θ(k·C(n,k)) hoặc Θ(n·n!) ký tự/phần tử tương ứng khi các phần tử phân biệt. Bộ nhớ của các bản liệt kê trả về danh sách trong code còn phải chứa toàn bộ đầu ra, không chỉ O(1) bộ nhớ phụ của phép biến đổi tại chỗ. Với n = 0, có đúng một xâu nhị phân rỗng và một hoán vị rỗng; k = 0 có một tổ hợp rỗng; k > n không có tổ hợp.

So sánh Sinh kế tiếp và Quay lui (Backtracking)

Lỗi hay gặp

Luyện ngay trên Big-O Coding

Thực hành các bài toán liệt kê tổ hợp và hoán vị trên hệ thống Big-O Coding:

Câu hỏi thường gặp

Nguồn tham khảo

• cppreference: std::next_permutation
• Python Documentation: itertools — Functions creating iterators
• Donald E. Knuth: The Art of Computer Programming, Volume 4A — Combinatorial Algorithms