Chương trình C++ phân tích số nguyên thành tổng các số dương

Chương trình liệt kê tất cả các cách phân tích một số nguyên dương n thành tổng các số nguyên dương (integer partitions), theo thứ tự không tăng.

Thuật toán

Hàm displayAllUniqueParts(m):
  Khởi tạo p[0] = m, k = 0.
  Lặp vô tận:
    In phân hoạch hiện tại p[0..k].
    Tìm vị trí k phải nhất có p[k] > 1.
    Nếu không có (tất cả là 1): dừng.
    Giảm p[k] đi 1, val = 1 + số lượng 1 đã bỏ qua.
    Phân chia val thành các phần có giá trị ≤ p[k] và thêm vào sau p[k].

Ví dụ mã nguồn

#include <iostream>
using namespace std;

void printArray(int p[], int m) {
    for (int i = 0; i < m; i++) cout << p[i] << " ";
    cout << endl;
}

void displayAllUniqueParts(int m) {
    int p[m];
    int k = 0;
    p[k] = m;
    while (true) {
        printArray(p, k+1);
        int val = 0;
        while (k >= 0 && p[k] == 1) {
            val += p[k];
            k--;
        }
        if (k < 0) return;
        p[k]--;
        val++;
        while (val > p[k]) {
            p[k+1] = p[k];
            val -= p[k];
            k++;
        }
        p[k+1] = val;
        k++;
    }
}

int main() {
    cout << "Cac phan tich cua so 7:\n";
    displayAllUniqueParts(7);
    return 0;
}

Đầu ra

7
6 1
5 2
5 1 1
4 3
4 2 1
4 1 1 1
3 3 1
3 2 2
3 2 1 1
3 1 1 1 1
2 2 2 1
2 2 1 1 1
2 1 1 1 1 1
1 1 1 1 1 1 1