C++ Program to Perform Integer Partition for a Specific Case

«
»

This is a C++ program to perform integer partition for a specific case.

Problem Description

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

Problem Solution

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

advertisement
Program/Source Code

C++ Program to perform integer partition for a specific case.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#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;
}
Program Explanation

1. Take the input of the natural number ‘n’.
2. Call PrintAllUniqueParts() with ‘i’ in the argument list.
3. Inside PrintAllUniqueParts(), declare an array p[] of length ‘n’ since we can generate maximum n partition, an element k to traverse in the array p[] and rem_val.
4. Assign n to the first element of array p[] and k to 0.
5. Now inside an infinite loop, print the array p[] and assign rem_val to 0, initially.
6. At the end of each iteration k Shifts to the end of the array to move it back to the first value encountered as greater than 0 and meanwhile add up all 1’s to rem_val.
7. If k reaches to -1 then breaks the loop and return to main.
8. To break value at k, decrement it and add it to rem_val.
9. So in the next loop, break rem_val till it is more than the value of index k, it will ignore the repetition.
10. Return to main.
11. Exit.

advertisement
Runtime Test Cases
Case 1:
Enter natural numbers for creating partitions: 5
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
 
Case 2:
Enter natural numbers for creating partitions: 8
All Unique Partitions of 8 are:-
        8
        7 1
        6 2
        6 1 1
        5 3
        5 2 1
        5 1 1 1
        4 4
        4 3 1
        4 2 2
        4 2 1 1
        4 1 1 1 1
        3 3 2
        3 3 1 1
        3 2 2 1
        3 2 1 1 1
        3 1 1 1 1 1
        2 2 2 2
        2 2 2 1 1
        2 2 1 1 1 1
        2 1 1 1 1 1 1
        1 1 1 1 1 1 1 1

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn