C++ प्रोग्राम: पूर्णांक पार्टीशन (Integer Partition) - विशिष्ट केस

यह C++ प्रोग्राम एक पॉजिटिव इंटीजर n के सभी संभावित यूनिक पार्टीशन (विभाजन) उत्पन्न करता है। पार्टीशन का अर्थ है n को पॉजिटिव इंटीजर्स के योग के रूप में दर्शाना, जहां क्रम का महत्व नहीं होता (जैसे 3+1 और 1+3 समान माने जाते हैं)।

एल्गोरिदम

शुरुआत
  1. फंक्शन displayAllUniqueParts(int m):
     1) पार्टीशन में अंतिम तत्व का इंडेक्स k = 0 सेट करें
     2) पहला पार्टीशन नंबर स्वयं इनिशियलाइज़ करें: p[k] = m
     3) व्हाइल लूप बनाएं जो पहले वर्तमान पार्टीशन प्रिंट करता है, फिर अगला पार्टीशन जनरेट करता है।
        लूप तब रुकता है जब वर्तमान पार्टीशन में सभी 1 हों।
     4) वर्तमान पार्टीशन displayArray(p, k+1) द्वारा प्रदर्शित करें
     5) अगला पार्टीशन जनरेट करें:
        - val = 0 इनिशियलाइज़ करें
        - p[] में दाएं से बाएं पहला नॉन-वन मान खोजें, val अपडेट करें
        - यदि k < 0, तो सभी मान 1 हैं, कोई और पार्टीशन नहीं, लौटें
        - मिले p[k] को घटाएं और val एडजस्ट करें
     6) यदि val अधिक है (सॉर्टेड ऑर्डर का उल्लंघन):
        - val को p[k] के आकार के विभिन्न मानों में विभाजित करें
        - इन मानों को p[k] के बाद अलग-अलग पोजीशन पर कॉपी करें
        - val को अगली पोजीशन पर कॉपी करें और पोजीशन इन्क्रीमेंट करें
समाप्ति

उदाहरण कोड

#include <iostream>
using namespace std;

void displayArray(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) {
        displayArray(p, k + 1);
        
        int val = 0;
        // दाएं से बाएं पहला नॉन-वन मान खोजें
        while (k >= 0 && p[k] == 1) {
            val += p[k];
            k--;
        }
        
        if (k < 0) return;  // सभी 1 हैं, समाप्त
        
        p[k]--;
        val++;
        
        // यदि val, p[k] से अधिक है तो विभाजित करें
        while (val > p[k]) {
            p[k + 1] = p[k];
            val = val - p[k];
            k++;
        }
        p[k + 1] = val;
        k++;
    }
}

int main() {
    cout << "Display All Unique Partitions of integer: 7\n";
    displayAllUniqueParts(7);
    return 0;
}

आउटपुट

Display All Unique Partitions of integer: 7
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

गणितीय पृष्ठभूमि: n=7 के लिए पार्टीशन की संख्या p(7) = 15 है। पार्टीशन फंक्शन p(n) तेजी से बढ़ता है: p(10)=42, p(20)=627, p(100)=190,569,292। यह एल्गोरिदम नॉन-इनक्रीसिंग ऑर्डर में पार्टीशन जनरेट करता है।