PHP-Fusion Powered Website

This is a C++ Program to find the unique partitions of a given integer such that the addition of a partition result an integer. Given a positive integer n, generate all possible unique ways to represent n as a sum of positive integers.

Here is source code of the C++ Program to demonstrate the Generation of All Unique Partitions of an Integer. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/* 
```

 * C++ Program to Generate All Unique Partitions of an Integer

```
 */
```
```
#include<iostream>
```
```
using namespace std;
```
```
/* 
```
```
 * print an array p[] of size 'n'
```
```
 */  
```
```
void printArray(int p[], int n)
```
```
{
```
```
    for (int i = 0; i < n; i++)
```
```
       cout << p[i] << " ";
```
```
    cout << endl;
```
```
}
```
```
 
```
```
void printAllUniqueParts(int n)
```
```
{
```

    int p[n]; // An array to store a partition

    int k = 0;  // Index of last element in a partition

    p[k] = n;  // Initialize first partition as number itself

```
 
```

    // This loop first prints the current partition then generates the next partition.

    // The loop stops when the current partition has all 1s

```
    while (true)
```
```
    {
```
```
        // print current partition
```
```
        printArray(p, k + 1);
```
```
 
```

        // Find the rightmost non-one value in p[]. Also, update the rem_val

        // So that we know how much value can be accommodated

```
 
```
```
        int rem_val = 0;
```
```
        while (k >= 0 && p[k] == 1)
```
```
        {
```
```
            rem_val += p[k];
```
```
            k--;
```
```
        }
```
```
 
```

        // if k < 0, all the values are 1 so there are no more partitions

```
 
```
```
        if (k < 0)  
```
```
            return;
```
```
 
```

        // Decrease the p[k] found above and adjust the rem_val

```
        p[k]--;
```
```
        rem_val++;
```
```
 
```

        // If rem_val is more, then the sorted order is violeted.

        // Divide rem_val in differnt values of size p[k]

        // Copy these values at different positions after p[k]

```
        while (rem_val > p[k])
```
```
        {
```
```
            p[k+1] = p[k];
```
```
            rem_val = rem_val - p[k];
```
```
            k++;
```
```
        }
```
```
 
```

        // Copy rem_val to next position and increment position

```
        p[k+1] = rem_val;
```
```
        k++;
```
```
    }
```
```
}
```
```
 
```
```
/* 
```
```
 * Main
```
```
 */
```
```
int main()
```
```
{
```
```
    int value;
```
```
    while(1)
```
```
    {
```

        cout<<"Enter an Integer(0 to exit): ";

```
        cin>>value;
```
```
        if (value == 0)
```
```
           break;
```

        cout << "All Unique Partitions of "<<value<<endl;

```
        printAllUniqueParts(value);
```
```
        cout<<endl;
```
```
    }
```
```
    return 0;
```
```
}
```

$ g++ unique_partitions.cpp
$ a.out
 
Enter an Integer(0 to exit): 2
All Unique Partitions of 2
2
1 1
 
Enter an Integer(0 to exit): 3
All Unique Partitions of 3
3
2 1
1 1 1
 
Enter an Integer(0 to exit): 4
All Unique Partitions of 4
4
3 1
2 2
2 1 1
1 1 1 1
 
Enter an Integer(0 to exit): 5
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
 
Enter an Integer(0 to exit): 7
All Unique Partitions of 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
 
Enter an Integer(0 to exit): 0
 
------------------
(program exited with code: 1)
Press return to continue

C++ Program to Perform Partition of an Integer in All Possible Ways