Users Online
· Guests Online: 97
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
Forum Threads
Newest Threads
No Threads created
Hottest Threads
No Threads created
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
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
Comments
No Comments have been Posted.
Post Comment
Please Login to Post a Comment.