PHP-Fusion Powered Website - Articles: C++ Program to Perform Partition of an Integer in All Possible Ways

Users Online

· Guests Online: 107

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads

No Threads created

Hottest Threads

No Threads created

Latest Articles

· Do while loop
· The for loop in C
· C while loop
· Pointers in C
· Functions in C

Oh no! Where's the JavaScript?
Your Web browser does not have JavaScript enabled or does not support JavaScript. Please enable JavaScript on your Web browser to properly view this Web site,
or upgrade to a Web browser that does support JavaScript; Firefox, Safari, Opera, Chrome or a version of Internet Explorer newer then version 6.

Articles Hierarchy

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

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

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

Users Online

Forum Threads

Latest Articles

Articles Hierarchy

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

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

Comments

Post Comment

Ratings