Bài 11.4: Sinh phân hoạch

Chào mừng trở lại với series blog về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ khám phá một chủ đề thú vị trong lĩnh vực tổ hợp (combinatorics): Sinh phân hoạch số nguyên. Bạn đã bao giờ tự hỏi có bao nhiêu cách để chia một số nguyên dương thành tổng của các số nguyên dương nhỏ hơn, mà không quan tâm đến thứ tự của các số hạng chưa? Đó chính là vấn đề phân hoạch số nguyên, và chúng ta sẽ tìm hiểu cách "sinh" ra tất cả các phân hoạch đó.

Phân hoạch Số nguyên là gì?

Một phân hoạch (partition) của một số nguyên dương n là một cách biểu diễn n dưới dạng tổng của các số nguyên dương. Điều _quan trọng_ là thứ tự của các số hạng trong tổng _không_ quan trọng.

Ví dụ: Phân hoạch của số 4 bao gồm:

4
3 + 1 (cũng như 1 + 3)
2 + 2
2 + 1 + 1 (cũng như 1 + 2 + 1, 1 + 1 + 2)
1 + 1 + 1 + 1

Để tránh lặp lại các phân hoạch chỉ khác nhau về thứ tự (như 3+1 và 1+3), theo quy ước, chúng ta thường biểu diễn các phân hoạch dưới dạng tổng của các số hạng được sắp xếp theo thứ tự _không tăng dần_ (hoặc không giảm dần).

Với quy ước này, các phân hoạch của 4 là:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

Số lượng các phân hoạch của n được ký hiệu là p(n). Ví dụ, p(4) = 5.

Hãy xem thêm vài ví dụ nhỏ:

Phân hoạch của 1: 1 (p(1) = 1)
Phân hoạch của 2: 2, 1 + 1 (p(2) = 2)
Phân hoạch của 3: 3, 2 + 1, 1 + 1 + 1 (p(3) = 3)
Phân hoạch của 5: 5, 4 + 1, 3 + 2, 3 + 1 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 (p(5) = 7)

Bài toán: Sinh tất cả các Phân hoạch của n

Bài toán của chúng ta là, cho một số nguyên dương n, hãy _sinh_ (liệt kê) tất cả các phân hoạch có thể có của n.

Đây là một bài toán kinh điển có thể giải quyết hiệu quả bằng kỹ thuật đệ quy kết hợp quay lui (recursion with backtracking). Ý tưởng chính là xây dựng từng phân hoạch một cách tuần tự, số hạng sau _không lớn hơn_ số hạng đứng trước nó để đảm bảo tính duy nhất.

Giải thuật Đệ quy Quay lui

Chúng ta sẽ xây dựng một hàm đệ quy có nhiệm vụ tìm kiếm các số hạng tiếp theo cho phân hoạch hiện tại. Hàm này cần biết:

Tổng còn lại cần phân hoạch (remaining_sum).
Phân hoạch đang được xây dựng (current_partition).
Số hạng lớn nhất được phép thêm vào ở bước hiện tại (max_allowed_term). Tham số này rất quan trọng để đảm bảo các số hạng theo thứ tự không tăng và tránh trùng lặp.

Cụ thể, hàm đệ quy của chúng ta có thể có dạng: generate_partitions(remaining_sum, current_partition, max_allowed_term).

Trường hợp cơ sở (Base Case): Nếu remaining_sum bằng 0, điều đó có nghĩa là chúng ta đã sử dụng hết tổng ban đầu và xây dựng được một phân hoạch hoàn chỉnh. Chúng ta in (hoặc lưu trữ) phân hoạch current_partition này.
Bước đệ quy (Recursive Step): Chúng ta cần thêm một số hạng dương term vào phân hoạch current_partition. Số hạng term này phải thỏa mãn hai điều kiện:
1. term phải nhỏ hơn hoặc bằng remaining_sum (chúng ta không thể dùng số lớn hơn tổng còn lại).
2. term phải nhỏ hơn hoặc bằng max_allowed_term (để duy trì thứ tự không tăng).
Vậy, chúng ta sẽ thử tất cả các giá trị term từ 1 cho đến min(remaining_sum, max_allowed_term). Với mỗi giá trị term hợp lệ:
1. Thêm term vào cuối current_partition.
2. Gọi đệ quy generate_partitions với tổng còn lại là remaining_sum - term, phân hoạch mới, và max_allowed_term cho bước tiếp theo là chính term vừa thêm vào (vì các số hạng sau term không được lớn hơn term).
3. Quay lui (Backtrack): Sau khi lời gọi đệ quy trả về (nghĩa là đã hoàn thành việc tìm kiếm các phân hoạch bắt đầu bằng các số hạng đã chọn), chúng ta phải xóa term khỏi current_partition để thử các giá trị term khác ở bước hiện tại.

Khi bắt đầu quá trình, chúng ta gọi hàm với generate_partitions(n, {}, n). Tham số max_allowed_term ban đầu là n vì số hạng đầu tiên có thể nhận bất kỳ giá trị nào từ 1 đến n.

C++ Code Minh hoạ

Dưới đây là cài đặt giải thuật sinh phân hoạch bằng C++:

#include <iostream>
#include <vector>
#include <numeric> // For accumulate (optional, just for demonstration)
#include <algorithm> // For min

// Hàm đệ quy để sinh phân hoạch
// remaining_sum: Tổng còn lại cần phân hoạch
// current_partition: Vector lưu trữ các số hạng của phân hoạch hiện tại
// max_allowed_term: Số hạng lớn nhất được phép thêm vào tiếp theo
void generate_partitions(int remaining_sum, vector<int>& current_partition, int max_allowed_term) {
    // Trường hợp cơ sở: Tổng còn lại bằng 0, đã tìm thấy một phân hoạch hoàn chỉnh
    if (remaining_sum == 0) {
        // In phân hoạch hiện tại
        for (size_t i = 0; i < current_partition.size(); ++i) {
            cout << current_partition[i] << (i == current_partition.size() - 1 ? "" : " + ");
        }
        cout << endl;
        return; // Kết thúc nhánh đệ quy này
    }

    // Bước đệ quy: Thử thêm các số hạng vào phân hoạch
    // term: Giá trị của số hạng tiếp theo
    // term bắt đầu từ 1 và kết thúc ở min(remaining_sum, max_allowed_term)
    for (int term = 1; term <= min(remaining_sum, max_allowed_term); ++term) {
        // Chọn term: Thêm số hạng hiện tại vào phân hoạch
        current_partition.push_back(term);

        // Gọi đệ quy: Tìm kiếm các số hạng tiếp theo
        // Tổng còn lại giảm đi term
        // Số hạng lớn nhất cho bước tiếp theo là term (để đảm bảo không tăng dần)
        generate_partitions(remaining_sum - term, current_partition, term);

        // Quay lui: Bỏ số hạng term vừa thêm vào để thử các giá trị khác
        current_partition.pop_back();
    }
}

int main() {
    int n;
    cout << "Nhap so nguyen duong n de sinh phan hoach: ";
    cin >> n;

    if (n <= 0) {
        cerr << "Vui long nhap mot so nguyen duong." << endl;
        return 1;
    }

    cout << "Cac phan hoach cua " << n << " la (theo thu tu khong tang dan):" << endl;

    // Khởi tạo vector rỗng cho phân hoạch ban đầu và gọi hàm đệ quy
    // max_allowed_term ban đầu là n, vì số hạng đầu tiên có thể là bất kỳ giá trị nào từ 1 đến n
    vector<int> initial_partition;
    generate_partitions(n, initial_partition, n);

    return 0;
}

Giải thích Code

#include <iostream>, <vector>, <numeric>, <algorithm>: Bao gồm các thư viện cần thiết cho nhập/xuất (iostream), sử dụng vector (vector), hàm min (algorithm). <numeric> không bắt buộc cho việc sinh, nhưng hữu ích nếu bạn muốn tính tổng vector.
generate_partitions(int remaining_sum, vector<int>& current_partition, int max_allowed_term): Đây là hàm đệ quy cốt lõi.
- remaining_sum: Lượng còn lại của n mà chúng ta cần chia nhỏ tiếp.
- current_partition: Một vector int được truyền bằng tham chiếu (&), dùng để xây dựng và lưu trữ các số hạng của phân hoạch hiện tại. Việc dùng tham chiếu giúp các lời gọi đệ quy cùng làm việc trên _một_ vector duy nhất, thêm/bớt phần tử khi cần.
- max_allowed_term: Giới hạn trên cho giá trị của số hạng term mà chúng ta có thể thêm vào ở bước này. Nó được truyền theo giá trị vì mỗi lời gọi đệ quy sẽ có giới hạn riêng.
if (remaining_sum == 0): Đây là điều kiện dừng của đệ quy. Nếu tổng còn lại là 0, chúng ta đã tìm thấy một tập hợp các số (current_partition) cộng lại bằng n. Chúng ta in nó ra và return để quay lại bước trước.
for (int term = 1; term <= min(remaining_sum, max_allowed_term); ++term): Vòng lặp này thử tất cả các giá trị có thể cho số hạng _tiếp theo_ trong phân hoạch.
- term bắt đầu từ 1 (số hạng phải là số nguyên dương).
- term <= remaining_sum: Đảm bảo chúng ta không thêm một số lớn hơn tổng còn lại.
- term <= max_allowed_term: Đây là _mấu chốt_ để đảm bảo thứ tự không tăng dần và tránh trùng lặp phân hoạch. Nếu số hạng trước đó là p_i, thì số hạng tiếp theo p_{i+1} phải <= p_i. max_allowed_term chính là p_i của bước trước. Khi chúng ta chọn term mới, max_allowed_term cho bước đệ quy tiếp theo sẽ là chính term này.
current_partition.push_back(term);: Thêm term vào cuối vector current_partition.
generate_partitions(remaining_sum - term, current_partition, term);: Lời gọi đệ quy để tiếp tục xây dựng phân hoạch.
- Tổng còn lại giảm đi term.
- current_partition đã có thêm term.
- max_allowed_term cho lần gọi này là term (số hạng tiếp theo không được lớn hơn term).
current_partition.pop_back();: Đây là bước quay lui. Sau khi lời gọi đệ quy generate_partitions trả về (nghĩa là nó đã khám phá tất cả các phân hoạch có thể bắt đầu bằng các số hạng hiện tại và term), chúng ta cần xóa term khỏi current_partition. Điều này cho phép vòng lặp for thử giá trị term tiếp theo, khám phá các nhánh phân hoạch khác.
main(): Hàm chính đọc n từ người dùng, kiểm tra n dương, in thông báo, và gọi hàm generate_partitions lần đầu tiên với n là tổng ban đầu, một vector rỗng, và n là số hạng lớn nhất ban đầu được phép (số hạng đầu tiên có thể là bất kỳ giá trị nào từ 1 đến n).

Chạy thử Ví dụ (n=4)

Hãy xem quá trình sinh phân hoạch cho n=4 diễn ra như thế nào với code trên:

Gọi generate_partitions(4, {}, 4)
- remaining_sum = 4, max_allowed_term = 4.
- Vòng lặp for term từ 1 đến min(4, 4) = 4.
- term = 1:
  - current_partition = {1}.
  - Gọi generate_partitions(3, {1}, 1)
    - remaining_sum = 3, max_allowed_term = 1.
    - Vòng lặp for term từ 1 đến min(3, 1) = 1.
    - term = 1:
      - current_partition = {1, 1}.
      - Gọi generate_partitions(2, {1, 1}, 1)
        
        remaining_sum = 2, max_allowed_term = 1.
        
        Vòng lặp for term từ 1 đến min(2, 1) = 1.
        
        term = 1:
        
        current_partition = {1, 1, 1}. Gọi generate_partitions(1, {1, 1, 1}, 1) remaining_sum = 1, max_allowed_term = 1. Vòng lặp for term từ 1 đến min(1, 1) = 1. term = 1: current_partition = {1, 1, 1, 1}. Gọi generate_partitions(0, {1, 1, 1, 1}, 1) remaining_sum = 0. Trường hợp cơ sở đạt được! In: 1 + 1 + 1 + 1. return. current_partition.pop_back() -> {1, 1, 1}. Vòng lặp term kết thúc. return. * current_partition.pop_back() -> {1, 1}.
        
        Vòng lặp term kết thúc. return.
      - current_partition.pop_back() -> {1}.
    - Vòng lặp term kết thúc. return.
  - current_partition.pop_back() -> {}.
- term = 2:
  - current_partition = {2}.
  - Gọi generate_partitions(2, {2}, 2)
    - remaining_sum = 2, max_allowed_term = 2.
    - Vòng lặp for term từ 1 đến min(2, 2) = 2.
    - term = 1:
      - current_partition = {2, 1}.
      - Gọi generate_partitions(1, {2, 1}, 1)
        
        remaining_sum = 1, max_allowed_term = 1.
        
        Vòng lặp for term từ 1 đến min(1, 1) = 1.
        
        term = 1:
        
        current_partition = {2, 1, 1}. Gọi generate_partitions(0, {2, 1, 1}, 1) remaining_sum = 0. Trường hợp cơ sở đạt được! In: 2 + 1 + 1. return. current_partition.pop_back() -> {2, 1}.
        
        Vòng lặp term kết thúc. return.
      - current_partition.pop_back() -> {2}.
    - term = 2:
      - current_partition = {2, 2}.
      - Gọi generate_partitions(0, {2, 2}, 2)
        
        remaining_sum = 0. Trường hợp cơ sở đạt được!
        
        In: 2 + 2.
        
        return.
      - current_partition.pop_back() -> {2}.
    - Vòng lặp term kết thúc. return.
  - current_partition.pop_back() -> {}.
- term = 3:
  - current_partition = {3}.
  - Gọi generate_partitions(1, {3}, 3)
    - remaining_sum = 1, max_allowed_term = 3.
    - Vòng lặp for term từ 1 đến min(1, 3) = 1.
    - term = 1:
      - current_partition = {3, 1}.
      - Gọi generate_partitions(0, {3, 1}, 1)
        
        remaining_sum = 0. Trường hợp cơ sở đạt được!
        
        In: 3 + 1.
        
        return.
      - current_partition.pop_back() -> {3}.
    - Vòng lặp term kết thúc. return.
  - current_partition.pop_back() -> {}.
- term = 4:
  - current_partition = {4}.
  - Gọi generate_partitions(0, {4}, 4)
    - remaining_sum = 0. Trường hợp cơ sở đạt được!
    - In: 4.
    - return.
  - current_partition.pop_back() -> {}.
- Vòng lặp term kết thúc. return.

Và kết quả in ra sẽ là các phân hoạch của 4 theo thứ tự (có thể khác thứ tự in trong ví dụ trace, tùy thuộc vào thứ tự duyệt của vòng lặp for, nhưng đều là 5 phân hoạch đó): 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.

Tại sao Phân hoạch Số nguyên lại quan trọng?

Sinh phân hoạch là một bài toán cơ bản trong tổ hợp. Mặc dù cài đặt đệ quy quay lui này có độ phức tạp tăng rất nhanh theo n (vì số lượng phân hoạch p(n) tăng trưởng theo hàm mũ), nó cung cấp một cách tiếp cận trực quan và hiệu quả để liệt kê tất cả các trường hợp.

Kiến thức về phân hoạch có ứng dụng trong nhiều lĩnh vực, từ lý thuyết số, lý thuyết biểu diễn nhóm, đến vật lý thống kê và cả trong các bài toán tin học như tối ưu hóa, đóng gói (bin packing - dù biến thể hơn).

Bài tập ví dụ:

[DSA-ThuatToanSinh].Mãy Gray 2.

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ó 2^3 mã Gray như sau: 000, 001, 011, 010, 110, 111, 101, 100. Hãy viết chương trình chuyển đổi một xâu mã nhị phân X có độ dài n thành một xâu mã Gray.

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 xâu nhị phân độ dài 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
01001
01110

Dữ liệu ra

01101
01001

Đây là hướng dẫn giải bài tập Mã Gray 2 bằng C++:

Quy tắc chuyển đổi Nhị phân sang Gray:
- Bit đầu tiên (Most Significant Bit - MSB) của mã Gray giống hệt bit đầu tiên của mã nhị phân.
- Các bit tiếp theo của mã Gray được tính bằng cách thực hiện phép toán XOR (^) giữa bit hiện tại và bit liền trước đó của mã nhị phân.
Cách thực hiện:
- Đọc số lượng test case T.
- Lặp lại T lần:
  - Đọc chuỗi nhị phân đầu vào (ví dụ: string binary_str).
  - Tạo một chuỗi kết quả (ví dụ: string gray_str) có cùng độ dài.
  - Ký tự đầu tiên của chuỗi Gray kết quả chính là ký tự đầu tiên của chuỗi nhị phân đầu vào (gray_str[0] = binary_str[0]).
  - Duyệt qua các ký tự còn lại của chuỗi nhị phân, bắt đầu từ ký tự thứ hai (chỉ số 1).
  - Tại mỗi vị trí i, để tính ký tự Gray thứ i (gray_str[i]), bạn cần thực hiện XOR giữa ký tự nhị phân tại vị trí i (binary_str[i]) và ký tự nhị phân tại vị trí i-1 (binary_str[i-1]).
  - Lưu ý: Các ký tự '0' và '1' cần được chuyển đổi thành số nguyên 0 và 1 trước khi thực hiện phép XOR, sau đó chuyển kết quả (0 hoặc 1) trở lại thành ký tự '0' hoặc '1'. Ví dụ: ('0' - '0') ^ ('1' - '0') sẽ cho kết quả 1, sau đó cộng '0' vào để có ký tự '1'.
  - Nối kết quả tính được vào chuỗi gray_str.
  - In chuỗi gray_str ra màn hình.
Gợi ý C++:
- Sử dụng string để lưu trữ chuỗi nhị phân và chuỗi Gray kết quả.
- Vòng lặp để xử lý T test case.
- Vòng lặp để duyệt qua các ký tự của chuỗi nhị phân từ chỉ số 1 đến cuối chuỗi.
- Sử dụng phép toán XOR (^) sau khi chuyển ký tự '0', '1' thành số 0, 1 (ví dụ: char_bit - '0').
- Chuyển kết quả XOR (0 hoặc 1) trở lại ký tự bằng cách cộng '0' (ví dụ: int_result + '0').

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

Comments

There are no comments at the moment.