โปรแกรม C++ แบ่งจำนวนเต็มเป็นผลรวมทุกแบบที่เป็นไปได้ (Integer Partition)

นี่คือโปรแกรม C++ เพื่อหาการแบ่ง (partition) ที่ไม่ซ้ำกันของจำนวนเต็มที่กำหนด ให้ผลรวมของการแบ่งได้จำนวนเต็มนั้น ในโปรแกรมนี้ จำนวนเต็มบวก n ถูกกำหนด และสร้างวิธีที่ไม่ซ้ำกันทั้งหมดในการแทน n เป็นผลรวมของจำนวนเต็มบวก

อัลกอริทึม

Begin
    function displayAllUniqueParts(int m):
        ประกาศอาร์เรย์เก็บ partition p[m]
        ตั้งค่า Index ของอิลีเมนต์สุดท้าย k ใน partition เป็น 0
        เริ่มต้น partition แรกเป็นตัวเลขเอง p[k] = m
        สร้าง while loop ที่พิมพ์ partition ปัจจุบัน แล้วสร้าง partition ถัดไป ลูปหยุดเมื่อ partition ปัจจุบันมีแต่ 1
        แสดง partition ปัจจุบันด้วย displayArray(p, k + 1)
        สร้าง partition ถัดไป:
            กำหนด val = 0
            หาค่าที่ไม่ใช่ 1 ขวาสุดใน p[] อัปเดต val ด้วยเพื่อรู้ว่าสามารถรองรับค่าได้เท่าไหร่
            ถ้า k < 0
                ค่าทั้งหมดเป็น 1 ไม่มี partition อีกแล้ว
            จบ if
            ลด p[k] ที่หาได้ และปรับ val
            ถ้า val มากกว่า
                ลำดับเรียงจะถูกละเมิด แบ่ง val เป็นค่าต่างๆ ขนาด p[k] และคัดลอกค่าเหล่านี้ไปตำแหน่งหลัง p[k]
            จบ if
            คัดลอก val ไปตำแหน่งถัดไป และเพิ่มตำแหน่ง
End

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

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

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

int main() {
    cout << "All Unique Partitions of 3\n";
    printAllUniqueParts(3);
    cout << "\nAll Unique Partitions of 4\n";
    printAllUniqueParts(4);
    cout << "\nAll Unique Partitions of 5\n";
    printAllUniqueParts(5);
    return 0;
}

ผลลัพธ์

All Unique Partitions of 3
3
2 1
1 1 1

All Unique Partitions of 4
4
3 1
2 2
2 1 1
1 1 1 1

All Unique Partitions of 5
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1