C++ Programming Code Examples

C++ > Beginners Lab Assignments Code Examples

Program to Perform Integer Partition for a Specific Case



Program to Perform Integer Partition for a Specific Case

- This algorithm generates all the possible partition can be generated by breaking the given integer value.
- The time complexity of this algorithm is O(n!).

- This algorithm takes the input of a natural number and prints all the possible partition.
- It starts with the number and breaks it by removing 1, at a time.
- Exit.

#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<<p[i]<<" ";
    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 "<<n<<" are:-\n";
	PrintAllUniqueParts(n);
 
    return 0;
}