Bài 11.3: Sinh tổ hợp

Chào mừng các bạn quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật của FullhouseDev! Hôm nay, chúng ta sẽ cùng nhau khám phá một chủ đề rất thú vị và có nhiều ứng dụng trong thực tế: Sinh tổ hợp (Generating Combinations).

Trong toán học, tổ hợp chập k của n phần tử là tập hợp con gồm k phần tử được lấy ra từ một tập hợp n phần tử phân biệt, không quan tâm đến thứ tự sắp xếp của các phần tử. Ví dụ, nếu chúng ta có tập {1, 2, 3, 4} và muốn tìm tất cả các tổ hợp chập 2, chúng ta sẽ có: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}. Có tất cả C(4, 2) = 4! / (2! * (4-2)!) = 6 tổ hợp.

Bài toán "Sinh tổ hợp" đặt ra là làm thế nào để liệt kê tất cả các tập hợp con gồm k phần tử này một cách có hệ thống. Đây là một bài toán cơ bản trong lĩnh vực giải thuật sinh (Generating Algorithms). Chúng ta sẽ đi sâu vào hai phương pháp phổ biến để giải quyết bài toán này: phương pháp quay lui đệ quy và phương pháp sinh kế tiếp theo thứ tự từ điển.

Hãy cùng bắt đầu!

Phương pháp 1: Quay lui đệ quy (Backtracking)

Phương pháp quay lui là một kỹ thuật giải quyết bài toán bằng cách xây dựng dần dần lời giải. Nếu tại một bước nào đó, ta nhận thấy rằng hướng đi hiện tại không thể dẫn đến lời giải hợp lệ, ta sẽ "quay lui" lại điểm quyết định trước đó và thử một hướng đi khác.

Với bài toán sinh tổ hợp, ý tưởng cốt lõi của quay lui là: để xây dựng một tổ hợp gồm k phần tử, ta sẽ chọn từng phần tử một. Tại mỗi bước, ta quyết định có chọn một phần tử vào tổ hợp hiện tại hay không chọn. Để tránh lặp lại và đảm bảo tính thứ tự (mặc dù tổ hợp không quan tâm thứ tự, nhưng việc chọn theo thứ tự giúp chúng ta sinh ra các tổ hợp phân biệt một cách có hệ thống), chúng ta thường chọn các phần tử theo thứ tự tăng dần từ tập nguồn.

Giả sử tập nguồn của chúng ta là các số nguyên từ 1 đến n. Chúng ta cần chọn k số.

Chúng ta có thể định nghĩa một hàm đệ quy generate_combinations(index, current_combination):

index: Chỉ số của phần tử bắt đầu xét trong tập nguồn cho lần chọn hiện tại. Điều này đảm bảo chúng ta chỉ chọn các phần tử có chỉ số lớn hơn hoặc bằng index để tránh lặp và giữ thứ tự tăng dần.
current_combination: Vector lưu trữ các phần tử đã chọn vào tổ hợp hiện tại.

Hàm này sẽ thực hiện các bước sau:

Trường hợp cơ sở (Base case): Nếu current_combination đã có đủ k phần tử, ta đã tìm được một tổ hợp. In hoặc lưu trữ tổ hợp này và kết thúc nhánh đệ quy hiện tại.
Trường hợp đệ quy: Nếu chưa đủ k phần tử, ta duyệt qua các phần tử từ index đến n.
- Với mỗi phần tử i (từ index đến n):
  - Chọn phần tử i: Thêm i vào current_combination.
  - Gọi đệ quy: generate_combinations(i + 1, current_combination). Ta gọi đệ quy với i + 1 vì ta chỉ được chọn các phần tử có chỉ số lớn hơn hoặc bằng i + 1 cho các vị trí tiếp theo của tổ hợp (do đã chọn i và muốn giữ thứ tự tăng dần).
  - Quay lui (Backtrack): Sau khi nhánh đệ quy kết thúc (dù nó có tìm được tổ hợp hay không), ta cần loại bỏ phần tử i khỏi current_combination để thử các khả năng khác (ví dụ: chọn phần tử khác thay vì i ở vị trí hiện tại).

Tuy nhiên, cách tiếp cận phổ biến và hiệu quả hơn với quay lui cho bài toán sinh tổ hợp là theo dõi số lượng phần tử cần chọn thêm.

Hàm đệ quy: generate_combinations(start_index, count_needed, current_combination)

start_index: Chỉ số của phần tử đầu tiên có thể được chọn trong tập nguồn cho bước hiện tại (từ 1 đến n).
count_needed: Số lượng phần tử còn cần phải chọn để hoàn thành tổ hợp.
current_combination: Vector lưu trữ các phần tử đã chọn vào tổ hợp hiện tại.

Các bước:

Trường hợp cơ sở: Nếu count_needed bằng 0, ta đã chọn đủ k phần tử. current_combination là một tổ hợp hợp lệ. In hoặc lưu trữ nó.
Trường hợp đệ quy:
- Chúng ta cần chọn count_needed phần tử nữa. Các phần tử này sẽ được chọn từ các phần tử có chỉ số từ start_index đến n.
- Số lượng phần tử còn lại để chọn từ start_index đến n là n - start_index + 1.
- Nếu số lượng phần tử còn lại (n - start_index + 1) ít hơn số lượng phần tử cần chọn (count_needed), thì không thể hoàn thành tổ hợp từ nhánh này. Dừng nhánh đệ quy.
- Duyệt qua các phần tử có thể chọn cho vị trí hiện tại, bắt đầu từ start_index. Một phần tử i (từ start_index đến n) có thể được chọn chỉ khi việc chọn nó vẫn cho phép chúng ta chọn đủ count_needed - 1 phần tử còn lại từ các phần tử có chỉ số lớn hơn i. Điều này có nghĩa là, nếu ta chọn phần tử i, thì từ i + 1 đến n, phải có ít nhất count_needed - 1 phần tử. Tức là n - (i + 1) + 1 >= count_needed - 1, hay n - i >= count_needed - 1, hoặc i <= n - (count_needed - 1). Vậy, vòng lặp sẽ chạy từ start_index đến n - count_needed + 1.
- Với mỗi phần tử i trong phạm vi hợp lệ:
  - Chọn phần tử i: Thêm i vào current_combination.
  - Gọi đệ quy: generate_combinations(i + 1, count_needed - 1, current_combination). Ta bắt đầu xét từ i + 1 cho lần chọn tiếp theo.
  - Quay lui: Loại bỏ phần tử i khỏi current_combination.

Hãy xem mã nguồn C++ minh họa cho phương pháp này:

#include <iostream>
#include <vector>
#include <numeric> // For std::iota (optional, for initial vector)

// Hàm đệ quy sinh tổ hợp
// n: tổng số phần tử trong tập nguồn (ví dụ: từ 1 đến n)
// k: số phần tử cần chọn cho mỗi tổ hợp
// start_index: chỉ số bắt đầu xét trong tập nguồn cho lần chọn hiện tại
// current_combination: vector lưu trữ các phần tử đã chọn
void generate_combinations_recursive(int n, int k, int start_index, std::vector<int>& current_combination) {
    // Trường hợp cơ sở: Đã chọn đủ k phần tử
    if (current_combination.size() == k) {
        // In tổ hợp hiện tại
        std::cout << "{ ";
        for (size_t i = 0; i < current_combination.size(); ++i) {
            std::cout << current_combination[i] << (i == current_combination.size() - 1 ? "" : ", ");
        }
        std::cout << " }" << std::endl;
        return; // Kết thúc nhánh đệ quy
    }

    // Trường hợp đệ quy: Duyệt qua các phần tử có thể chọn
    // i bắt đầu từ start_index
    // Điều kiện i <= n - (k - current_combination.size())
    // n: tổng số phần tử
    // k - current_combination.size(): số lượng phần tử CẦN chọn thêm
    // n - (k - current_combination.size()): chỉ số LỚN NHẤT mà phần tử hiện tại (i) có thể nhận
    // để vẫn còn đủ phần tử sau nó (từ i+1 đến n) cho các lựa chọn tiếp theo
    for (int i = start_index; i <= n - (k - current_combination.size()); ++i) {
        // 1. Chọn phần tử i
        current_combination.push_back(i);

        // 2. Gọi đệ quy với start_index_mới = i + 1 (chỉ xét các phần tử sau i)
        // và số lượng đã chọn tăng lên
        generate_combinations_recursive(n, k, i + 1, current_combination);

        // 3. Quay lui: Loại bỏ phần tử i để thử khả năng khác
        current_combination.pop_back();
    }
}

// Hàm bao ngoài để bắt đầu quá trình sinh tổ hợp đệ quy
void find_combinations_recursive(int n, int k) {
    if (k < 0 || k > n) {
        std::cerr << "Lỗi: k phải nằm trong khoảng [0, n]" << std::endl;
        return;
    }
    std::vector<int> current_combination;
    // Bắt đầu xét các phần tử từ 1
    generate_combinations_recursive(n, k, 1, current_combination);
}

/*
// Ví dụ sử dụng
int main() {
    int n = 4;
    int k = 2;
    std::cout << "Sinh tat ca to hop chap " << k << " cua " << n << " phan tu (1.." << n << ") bang de quy:" << std::endl;
    find_combinations_recursive(n, k);

    n = 5;
    k = 3;
    std::cout << "\nSinh tat ca to hop chap " << k << " cua " << n << " phan tu (1.." << n << ") bang de quy:" << std::endl;
    find_combinations_recursive(n, k);

    return 0;
}
*/

Giải thích mã nguồn đệ quy:

Hàm generate_combinations_recursive(n, k, start_index, current_combination):
- n, k: Giữ nguyên giá trị gốc của bài toán.
- start_index: Quan trọng. Nó là chỉ số của phần tử nhỏ nhất trong tập nguồn (1 đến n) mà chúng ta được phép chọn ở bước hiện tại. Bằng cách bắt đầu vòng lặp từ start_index, chúng ta đảm bảo các phần tử trong current_combination luôn theo thứ tự tăng dần, và mỗi tổ hợp chỉ được sinh ra một lần.
- current_combination: Là vector lưu trữ các phần tử đã chọn đến thời điểm hiện tại trong quá trình đệ quy.
Điều kiện dừng đệ quy: if (current_combination.size() == k): Khi kích thước của current_combination bằng k, tức là chúng ta đã chọn đủ số lượng phần tử cần thiết, một tổ hợp hợp lệ đã được tìm thấy. Ta in nó ra và trở về (return).
Vòng lặp for: for (int i = start_index; i <= n - (k - current_combination.size()); ++i):
- Duyệt qua các phần tử tiềm năng để thêm vào tổ hợp ở bước hiện tại.
- i bắt đầu từ start_index vì ta không muốn chọn lại các phần tử nhỏ hơn start_index (chúng đã được xét ở các bước trước hoặc không được chọn).
- Điều kiện i <= n - (k - current_combination.size()): Đây là phần hạn chế quan trọng. k - current_combination.size() là số lượng phần tử còn thiếu cần chọn. Nếu ta chọn phần tử i, thì các phần tử tiếp theo phải được chọn từ tập i+1, i+2, ..., n. Số lượng phần tử trong tập này là n - (i + 1) + 1 = n - i. Ta cần n - i phải đủ lớn để chọn được k - current_combination.size() - 1 phần tử nữa (vì i đã được chọn). Tức là n - i >= (k - current_combination.size()) - 1, suy ra n - i >= k - current_combination.size() - 1. Chuyển vế i <= n - (k - current_combination.size() - 1), hay i <= n - k + current_combination.size() + 1. Oops, công thức trong code là n - (k - current_combination.size()). Hãy xem xét lại điều kiện.
- Điều kiện i <= n - (k - current_combination.size()) có thể hiểu đơn giản hơn: Nếu ta chọn phần tử i, thì còn k - current_combination.size() vị trí cần điền. Các vị trí này sẽ được điền bằng các số từ i+1 đến n. Số lượng số từ i+1 đến n là n - i. Ta cần n - i phải lớn hơn hoặc bằng số phần tử còn thiếu này trừ đi 1 (vì phần tử i đã được chọn). Tức là n - i >= (k - current_combination.size()) - 1. Hoặc, nếu nhìn theo số phần tử còn lại để chọn: ta cần chọn count_needed = k - current_combination.size() phần tử nữa. Nếu chọn i, thì ta còn cần chọn count_needed - 1 phần tử từ tập {i+1, ..., n}. Tập này có n - i phần tử. Vậy ta cần n - i >= count_needed - 1. Suy ra i <= n - count_needed + 1. Thay count_needed = k - current_combination.size(), ta được i <= n - (k - current_combination.size()) + 1. OK, có vẻ công thức trong code thiếu +1.
- Hãy sửa lại điều kiện trong code hoặc giải thích cho đúng với code. Điều kiện i <= n - (k - current_combination.size()) thực ra là i <= n - k + current_combination.size(). Tại sao? Nếu ta chọn i, ta cần chọn k - current_combination.size() phần tử nữa. Các phần tử này phải ít nhất là i+1, i+2, ..., i + (k - current_combination.size()). Phần tử cuối cùng trong nhóm này sẽ có giá trị là i + k - current_combination.size(). Giá trị này phải nhỏ hơn hoặc bằng n. Tức là i + k - current_combination.size() <= n. Suy ra i <= n - k + current_combination.size(). Vậy điều kiện trong code là chính xác! Nó đảm bảo rằng từ vị trí i trở đi, vẫn còn đủ số lượng phần tử (n - i + 1) để hoàn thành tổ hợp (k - current_combination.size() phần tử cần chọn).
current_combination.push_back(i): Thêm phần tử i vào tổ hợp tạm thời.
generate_combinations_recursive(n, k, i + 1, current_combination): Gọi đệ quy để tiếp tục xây dựng tổ hợp. start_index mới là i + 1 để đảm bảo các phần tử tiếp theo được chọn lớn hơn i.
current_combination.pop_back(): Sau khi nhánh đệ quy trả về (dù nó tìm được tổ hợp hay không), ta loại bỏ phần tử i khỏi tổ hợp tạm thời. Đây là bước "quay lui", cho phép chúng ta thử chọn phần tử khác ở vị trí hiện tại.

Ưu điểm của phương pháp quay lui là tính trực quan và dễ hiểu, đặc biệt khi được triển khai bằng đệ quy. Nhược điểm là nó có thể tốn bộ nhớ cho stack đệ quy nếu k hoặc n quá lớn.

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

Phương pháp này hoạt động bằng cách bắt đầu từ tổ hợp đầu tiên (theo một thứ tự nào đó, thường là thứ tự từ điển/tăng dần) và sau đó tìm cách "sinh" ra tổ hợp tiếp theo một cách có hệ thống cho đến khi hết.

Với tập nguồn là {1, 2, ..., n} và cần chọn k phần tử, tổ hợp đầu tiên theo thứ tự từ điển là {1, 2, ..., k}.

Để tìm tổ hợp kế tiếp của một tổ hợp hiện tại {c_1, c_2, ..., c_k} (với c_1 < c_2 < ... < c_k), chúng ta thực hiện các bước sau:

Tìm phần tử c_i từ phải sang trái (tức là duyệt i từ k về 1) sao cho c_i chưa đạt giá trị lớn nhất có thể tại vị trí của nó. Giá trị lớn nhất có thể của c_i là n - (k - i). Ví dụ, phần tử cuối cùng c_k có giá trị lớn nhất là n. Phần tử c_{k-1} có giá trị lớn nhất là n-1 (để dành n cho c_k). Phần tử c_i có giá trị lớn nhất là n - (số phần tử còn lại sau nó) = n - (k - i).
Nếu không tìm thấy phần tử nào như vậy (tức là i trở thành 0), điều đó có nghĩa là tổ hợp hiện tại là tổ hợp cuối cùng (theo thứ tự từ điển), đó là {n-k+1, n-k+2, ..., n}. Quá trình dừng lại.
Nếu tìm thấy c_i, ta tăng giá trị của nó lên 1: c_i = c_i + 1.
Sau khi tăng c_i, các phần tử đứng sau nó (c_{i+1}, ..., c_k) phải được đặt lại thành các giá trị nhỏ nhất có thể theo thứ tự tăng dần, bắt đầu từ c_i + 1. Nghĩa là, c_{i+1} = c_i + 1, c_{i+2} = c_i + 2, ..., c_k = c_i + (k - i).

Hãy xem mã nguồn C++ minh họa cho phương pháp này:

#include <iostream>
#include <vector>
#include <numeric> // For std::iota (optional, for initial vector)
#include <algorithm> // For std::min (optional)

// Hàm in một tổ hợp
void print_combination(const std::vector<int>& combination) {
    std::cout << "{ ";
    for (size_t i = 0; i < combination.size(); ++i) {
        std::cout << combination[i] << (i == combination.size() - 1 ? "" : ", ");
    }
    std::cout << " }" << std::endl;
}

// Hàm sinh tất cả tổ hợp chập k của n phần tử (1..n) bằng phương pháp sinh kế tiếp
void find_combinations_iterative(int n, int k) {
    if (k < 0 || k > n) {
        std::cerr << "Lỗi: k phải nằm trong khoảng [0, n]" << std::endl;
        return;
    }
    if (k == 0) { // Trường hợp đặc biệt: chỉ có 1 tổ hợp rỗng
        print_combination({});
        return;
    }
    if (k == n) { // Trường hợp đặc biệt: chỉ có 1 tổ hợp là cả tập
        std::vector<int> combination(n);
        std::iota(combination.begin(), combination.end(), 1); // combination = {1, 2, ..., n}
        print_combination(combination);
        return;
    }

    // Khởi tạo tổ hợp đầu tiên: {1, 2, ..., k}
    std::vector<int> current_combination(k);
    std::iota(current_combination.begin(), current_combination.end(), 1); // combination = {1, 2, ..., k}

    // Vòng lặp sinh các tổ hợp kế tiếp
    while (true) {
        // 1. In tổ hợp hiện tại
        print_combination(current_combination);

        // 2. Tìm phần tử c[i] từ phải sang trái có thể tăng giá trị
        int i = k - 1; // Bắt đầu từ phần tử cuối cùng
        // Duyệt từ k-1 về 0
        // current_combination[i] < n - (k - 1 - i) == n - k + 1 + i
        // n - k + 1 + i là giá trị lớn nhất mà phần tử ở vị trí i có thể nhận
        while (i >= 0 && current_combination[i] >= n - k + 1 + i) {
            i--;
        }

        // 3. Nếu i < 0, tức là không tìm thấy phần tử nào có thể tăng
        // Đã đến tổ hợp cuối cùng {n-k+1, ..., n}. Dừng vòng lặp.
        if (i < 0) {
            break;
        }

        // 4. Tăng giá trị của phần tử tìm được (tại chỉ số i)
        current_combination[i]++;

        // 5. Đặt lại các phần tử sau c[i] về giá trị nhỏ nhất có thể
        // c[j] = c[i] + (j - i) với j từ i+1 đến k-1
        for (int j = i + 1; j < k; ++j) {
            current_combination[j] = current_combination[j - 1] + 1;
            // Hoặc cách khác: current_combination[j] = current_combination[i] + (j - i);
        }
    }
}

/*
// Ví dụ sử dụng
int main() {
    int n = 4;
    int k = 2;
    std::cout << "Sinh tat ca to hop chap " << k << " cua " << n << " phan tu (1.." << n << ") bang sinh ke tiep:" << std::endl;
    find_combinations_iterative(n, k);

    n = 5;
    k = 3;
    std::cout << "\nSinh tat ca to hop chap " << k << " cua " << n << " phan tu (1.." << n << ") bang sinh ke tiep:" << std::endl;
    find_combinations_iterative(n, k);

    return 0;
}
*/

Giải thích mã nguồn sinh kế tiếp:

Hàm find_combinations_iterative(n, k):
- Xử lý các trường hợp đặc biệt k=0 và k=n.
- Khởi tạo current_combination là vector có kích thước k, chứa các giá trị từ 1 đến k (std::iota giúp làm việc này nhanh chóng). Đây là tổ hợp đầu tiên.
Vòng lặp while (true): Tiếp tục sinh tổ hợp cho đến khi không thể sinh được nữa (điều kiện break).
- print_combination(current_combination): In tổ hợp vừa được sinh ra hoặc khởi tạo.
- int i = k - 1;: Bắt đầu tìm từ phần tử cuối cùng của tổ hợp.
- while (i >= 0 && current_combination[i] >= n - k + 1 + i): Vòng lặp này tìm chỉ số i từ phải sang trái (i--). Nó dừng lại khi tìm thấy phần tử current_combination[i] chưa đạt giá trị lớn nhất có thể tại vị trí i.
  - Giá trị lớn nhất có thể của phần tử tại chỉ số i trong một tổ hợp tăng dần là n - (số phần tử còn lại sau nó). Số phần tử còn lại sau current_combination[i] là k - 1 - i. Vậy giá trị lớn nhất là n - (k - 1 - i).
  - Điều kiện current_combination[i] >= n - (k - 1 - i) có nghĩa là phần tử tại i đã đạt hoặc vượt quá giá trị lớn nhất có thể. Ta cần lùi lại i để tìm phần tử có thể tăng.
- if (i < 0): Nếu vòng lặp while chạy hết mà i nhỏ hơn 0, nghĩa là tất cả các phần tử đã đạt giá trị lớn nhất có thể (tổ hợp là {n-k+1, ..., n}). Ta break khỏi vòng lặp while.
- current_combination[i]++;: Tăng giá trị của phần tử tại chỉ số i lên 1. Đây là bước "nhảy" sang tổ hợp kế tiếp.
- for (int j = i + 1; j < k; ++j): Sau khi tăng current_combination[i], các phần tử sau nó phải được "đặt lại" để tạo ra tổ hợp nhỏ nhất tiếp theo theo thứ tự từ điển. Các phần tử này sẽ là current_combination[i] + 1, current_combination[i] + 2, ..., current_combination[i] + (k - 1 - i). Vòng lặp này thực hiện việc đó.

Ưu điểm của phương pháp sinh kế tiếp là nó không sử dụng đệ quy, tránh được overhead và giới hạn của stack đệ quy. Nó thường hiệu quả về mặt bộ nhớ. Tuy nhiên, việc suy ra công thức và triển khai logic sinh kế tiếp có thể kém trực quan hơn so với quay lui đệ quy.

Ví dụ Minh Họa Tổng Hợp

Để thấy rõ hơn cách cả hai phương pháp hoạt động, chúng ta sẽ chạy thử với cùng một bộ tham số n=4, k=2 và n=5, k=3.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// --- Mã nguồn Quay lui đệ quy (như trên) ---

void generate_combinations_recursive(int n, int k, int start_index, std::vector<int>& current_combination) {
    if (current_combination.size() == k) {
        std::cout << "{ ";
        for (size_t i = 0; i < current_combination.size(); ++i) {
            std::cout << current_combination[i] << (i == current_combination.size() - 1 ? "" : ", ");
        }
        std::cout << " }" << std::endl;
        return;
    }

    for (int i = start_index; i <= n - (k - current_combination.size()); ++i) {
        current_combination.push_back(i);
        generate_combinations_recursive(n, k, i + 1, current_combination);
        current_combination.pop_back();
    }
}

void find_combinations_recursive(int n, int k) {
    if (k < 0 || k > n) {
        std::cerr << "Lỗi: k phải nằm trong khoảng [0, n]" << std::endl;
        return;
    }
     if (k == 0) {
        std::cout << "{ }" << std::endl;
        return;
    }
    std::vector<int> current_combination;
    generate_combinations_recursive(n, k, 1, current_combination);
}

// --- Mã nguồn Sinh kế tiếp (như trên) ---

void print_combination(const std::vector<int>& combination) {
    std::cout << "{ ";
    for (size_t i = 0; i < combination.size(); ++i) {
        std::cout << combination[i] << (i == combination.size() - 1 ? "" : ", ");
    }
    std::cout << " }" << std::endl;
}

void find_combinations_iterative(int n, int k) {
    if (k < 0 || k > n) {
        std::cerr << "Lỗi: k phải nằm trong khoảng [0, n]" << std::endl;
        return;
    }
    if (k == 0) {
        print_combination({});
        return;
    }
    if (k == n) {
        std::vector<int> combination(n);
        std::iota(combination.begin(), combination.end(), 1);
        print_combination(combination);
        return;
    }

    std::vector<int> current_combination(k);
    std::iota(current_combination.begin(), current_combination.end(), 1);

    while (true) {
        print_combination(current_combination);

        int i = k - 1;
        while (i >= 0 && current_combination[i] >= n - k + 1 + i) {
            i--;
        }

        if (i < 0) {
            break;
        }

        current_combination[i]++;
        for (int j = i + 1; j < k; ++j) {
            current_combination[j] = current_combination[j - 1] + 1;
        }
    }
}


int main() {
    int n1 = 4, k1 = 2;
    std::cout << "--- Sinh tat ca to hop chap " << k1 << " cua " << n1 << " phan tu (1.." << n1 << ") ---" << std::endl;
    std::cout << "\nBang phuong phap DE QUY QUAY LUI:" << std::endl;
    find_combinations_recursive(n1, k1);

    std::cout << "\nBang phuong phap SINH KE TIEP:" << std::endl;
    find_combinations_iterative(n1, k1);

    std::cout << "\n=========================================" << std::endl;

    int n2 = 5, k2 = 3;
    std::cout << "--- Sinh tat ca to hop chap " << k2 << " cua " << n2 << " phan tu (1.." << n2 << ") ---" << std::endl;
    std::cout << "\nBang phuong phap DE QUY QUAY LUI:" << std::endl;
    find_combinations_recursive(n2, k2);

    std::cout << "\nBang phuong phap SINH KE TIEP:" << std::endl;
    find_combinations_iterative(n2, k2);

    return 0;
}

Kết quả chạy chương trình:

--- Sinh tat ca to hop chap 2 cua 4 phan tu (1..4) ---

Bang phuong phap DE QUY QUAY LUI:
{ 1, 2 }
{ 1, 3 }
{ 1, 4 }
{ 2, 3 }
{ 2, 4 }
{ 3, 4 }

Bang phuong phap SINH KE TIEP:
{ 1, 2 }
{ 1, 3 }
{ 1, 4 }
{ 2, 3 }
{ 2, 4 }
{ 3, 4 }

=========================================
--- Sinh tat ca to hop chap 3 cua 5 phan tu (1..5) ---

Bang phuong phap DE QUY QUAY LUI:
{ 1, 2, 3 }
{ 1, 2, 4 }
{ 1, 2, 5 }
{ 1, 3, 4 }
{ 1, 3, 5 }
{ 1, 4, 5 }
{ 2, 3, 4 }
{ 2, 3, 5 }
{ 2, 4, 5 }
{ 3, 4, 5 }

Bang phuong phap SINH KE TIEP:
{ 1, 2, 3 }
{ 1, 2, 4 }
{ 1, 2, 5 }
{ 1, 3, 4 }
{ 1, 3, 5 }
{ 1, 4, 5 }
{ 2, 3, 4 }
{ 2, 3, 5 }
{ 2, 4, 5 }
{ 3, 4, 5 }

Như bạn có thể thấy, cả hai phương pháp đều cho ra kết quả giống nhau, liệt kê tất cả các tổ hợp chập k của n phần tử. Phương pháp sinh kế tiếp liệt kê theo thứ tự từ điển một cách tự nhiên. Phương pháp đệ quy quay lui cũng có thể tạo ra thứ tự từ điển nếu chúng ta duyệt các phần tử tiềm năng (i) theo thứ tự tăng dần như đã làm trong code.

Lựa chọn Phương pháp nào?

Quay lui đệ quy: Thường dễ hiểu và triển khai hơn cho người mới bắt đầu hoặc khi bài toán có thêm các ràng buộc phức tạp khác (ví dụ: sinh tổ hợp có tổng bằng một giá trị nào đó). Tuy nhiên, có thể gặp vấn đề về bộ nhớ (stack overflow) với n lớn hoặc k gần n/2 do độ sâu đệ quy.
Sinh kế tiếp: Hiệu quả hơn về bộ nhớ vì không dùng stack đệ quy (ngoại trừ stack của main). Nó phù hợp khi bạn cần duyệt qua tất cả các tổ hợp một cách hiệu quả và có thể dễ dàng tích hợp vào các vòng lặp lớn hơn. Việc triển khai có thể hơi khó hiểu hơn ban đầu do phải suy luận logic sinh tổ hợp kế tiếp.

Bài tập ví dụ:

[DSA-ThuatToanSinh].Mã Gray 1.

Số nhị phân được xem là cách mặc định biểu diễn các số. Tuy nhiên, trong nhiều ứng dụng của điện tử và truyền thông lại dùng một biến thể của mã nhị phân đó là mã Gray. Mã Gray độ dài n có mã đầu tiên là n số 0, mã kế tiếp của nó là một xâu nhị phân độ dài n khác biệt với xâu trước đó một bít. Ví dụ với n=3 ta có 23 mã Gray như sau: 000, 001, 011, 010, 110, 111, 101, 100. Hãy viết chương trình liệt kê các mã Gray có độ dài n.

Input Format

-Dòng đầu tiên là số lượng test T. - T dòng kế tiếp ghi lại mỗi dòng một test. Mỗi test là một số tự nhiên n. T, n thỏa mãn ràng buộc: 1≤T, n≤10.

Constraints

Output Format

Đưa ra kết quả mỗi test theo từng dòng.

Ví dụ:

Dữ liệu vào

2
3
4

Dữ liệu ra

000 001 011 010 110 111 101 100
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

```markdown Tuyệt vời! Đây là hướng dẫn giải bài toán Mã Gray 1 bằng C++ một cách ngắn gọn, tập trung vào ý tưởng thuật toán mà không cung cấp code hoàn chỉnh:

Hướng giải:

Ý tưởng chính: Có một công thức toán học (sử dụng phép toán bitwise) cho phép chuyển trực tiếp một số nguyên từ hệ nhị phân thông thường sang mã Gray tương ứng. Để liệt kê tất cả mã Gray độ dài n, ta có thể liệt kê tất cả các số nguyên từ 0 đến 2^n - 1, chuyển từng số sang mã Gray và in ra dưới dạng chuỗi nhị phân.
Công thức chuyển đổi: Mã Gray G của một số nguyên i (trong hệ nhị phân thông thường) được tính bằng công thức: G = i ^ (i >> 1). Trong đó ^ là phép XOR bitwise, và >> 1 là dịch bit sang phải 1 vị trí.
Các bước thực hiện cho mỗi test case với độ dài n:
- Tính tổng số lượng mã Gray cần tạo là total_codes = 2^n.
- Lặp một vòng lặp với biến đếm i từ 0 đến total_codes - 1.
- Trong mỗi lần lặp:
  - Áp dụng công thức gray_val = i ^ (i >> 1) để tính giá trị mã Gray tương ứng với số i.
  - Chuyển giá trị số nguyên gray_val này thành một chuỗi nhị phân có độ dài đúng bằng n. Điều này có thể được thực hiện bằng cách duyệt qua các bit của gray_val từ bit thứ n-1 xuống 0, hoặc sử dụng các kỹ thuật khác để đảm bảo chuỗi có đủ n ký tự '0' hoặc '1' (ví dụ: thêm '0' vào đầu nếu cần).
  - In chuỗi nhị phân vừa tạo, theo sau là một dấu cách.
- Sau khi kết thúc vòng lặp (đã in hết 2^n mã), in một ký tự xuống dòng để kết thúc output cho test case này.
Xử lý nhiều test case: Đọc số lượng test T và lặp lại các bước trên T lần.

Lưu ý:

Bạn cần cài đặt cách chuyển đổi một số nguyên thành chuỗi nhị phân có độ dài cố định n (bao gồm việc thêm các bit '0' dẫn đầu nếu giá trị nhỏ).
Sử dụng kiểu dữ liệu phù hợp cho i và gray_val (ví dụ: int đủ cho n<=10).

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.