C++ प्रोग्राम: एक इंटीजर के सभी संभावित तरीकों से पार्टीशन करना

यहां एक C++ प्रोग्राम है जो दिए गए इंटीजर के सभी यूनिक पार्टीशन प्राप्त करता है जैसे कि एक पार्टीशन का योग एक इंटीजर परिणाम देता है। इस प्रोग्राम में, एक पॉजिटिव इंटीजर n दिया जाता है, और n को पॉजिटिव इंटीजर्स के योग के रूप में प्रस्तुत करने के सभी संभावित यूनिक तरीके जनरेट करें।

एल्गोरिदम

Begin
    function displayAllUniqueParts(int m):
        एक पार्टीशन स्टोर करने के लिए ऐरे घोषित करें p[m]।
        एक पार्टीशन में अंतिम एलिमेंट का इंडेक्स k को 0 पर सेट करें
        पहली पार्टीशन को संख्या के रूप में इनिशियलाइज़ करें, p[k] = m
        एक व्हाइल लूप बनाएं जो पहले वर्तमान पार्टीशन को प्रिंट करता है, फिर अगली पार्टीजन जनरेट करता है। लूप तब रुकता है जब वर्तमान पार्टीशन में सभी 1 होते हैं।
        वर्तमान पार्टीशन को displayArray(p, k + 1) के रूप में प्रदर्शित करें
        अगली पार्टीशन जनरेट करें:
        val = 0 इनिशियलाइज़ करें।
        p[] में राइटमोस्ट नॉन-वन वैल्यू ढूंढें। साथ ही, val को अपडेट करें ताकि हम जान सकें कि कितना वैल्यू समायोजित किया जा सकता है।
        यदि k < 0, तो
            सभी वैल्यू 1 हैं इसलिए कोई और पार्टीशन नहीं हैं
            ऊपर पाए गए p[k] को घटाएं और val को एडजस्ट करें।
        यदि val अधिक है,
            तो सॉर्टेड ऑर्डर वायलेट होता है। val को p[k] के आकार के अलग-अलग वैल्यू में विभाजित करें और इन वैल्यू को p[k] के बाद अलग-अलग पोजीशन पर कॉपी करें।
            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