C++ Program to Generate All the Set Partitions of n Numbers Beginning from 1 and so on

Code:

#include    iostream

using namespace std;

// A function to print the generated partition.
void printArray(int p[], int n)
{
cout<<"\t";
for (int i = 0; i < n; i++)
cout<

    cout<<"\n";
}

// A function to print all the possible partition.
void PrintAllUniqueParts(int n)
{
    int p[n], k = 0;
    p[k] = n;
    // Loop until all the array elements converted to 1 mean no further partition can be generated.
    while(1)
    {
        printArray(p, k + 1);
        int rem_val = 0;

        // Move the pointer to the index so that p[k] > 1.
        while (k >= 0 && p[k] == 1)
        {
            rem_val += p[k];
k--;
        }
        // If k < 0 then the all the element are broken down to 1.
        if (k < 0)  
            return;

        // If value greater than 1 is found then decrease it by 1 and increase rem_val to add it to other elements.
        p[k]--;
        rem_val++;

        // Loop until the number of 1's are greater than the value at k index.
        while (rem_val > p[k])
        {
            p[k+1] = p[k];
            // Decrease the rem_val value.
            rem_val = rem_val - p[k];
            k++;
        }

        // Assign the remaining value to the index next to k.
        p[k+1] = rem_val;
        k++;
    }
}

int main()
{
    int n;
    cout<<"Enter natural numbers for creating partitions: ";
cin>>n;
if (value <= 0)
{
cout<<"Wrong input!!";
break;
}
cout<<"All Unique Partitions of "<
PrintAllUniqueParts(n);

    return 0;
}



Output:

Case 1:
Enter natural numbers for creating partitions: 3

All Unique Partitions of 1 are:-
        1

All Unique Partitions of 2 are:-
        2
        1 1

All Unique Partitions of 3 are:-
        3
        2 1
        1 1 1


Case 2:
Enter natural numbers for creating partitions: 5

All Unique Partitions of 1 are:-
        1

All Unique Partitions of 2 are:-
        2
        1 1

All Unique Partitions of 3 are:-
        3
        2 1
        1 1 1

All Unique Partitions of 4 are:-
        4
        3 1
        2 2
        2 1 1
        1 1 1 1

All Unique Partitions of 5 are:-
        5
        4 1
        3 2
        3 1 1
        2 2 1
        2 1 1 1
        1 1 1 1 1



More C++ Programs: