Code:
#include iostream
using namespace std;
// A function to count all the possible partition.
int CountPartitions(int n)
{
int p[n], k = 0, count = -1;
p[k] = n;
// Loop until all the array elements converted to 1 mean no further partition can be generated.
while(1)
{
count++;
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 count;
// 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, c;
cout<<"Enter natural numbers for partition counting: ";
cin>>n;
if (n <= 0)
{
cout<<"Wrong input!!";
return 0;
}
c = CountPartitions(n);
cout<<"The number of partitions of with each element lesser than "<
return 0;
}
Output:
Case 1:
Enter natural numbers for partition counting: 10
The number of partitions of with each element lesser than 10 is:- 41
Case 2:
Enter natural numbers for creating partitions: 50
The number of partitions of with each element lesser than 50 is:- 204225
Case 3:
Enter natural numbers for partition counting: 100
The number of partitions of with each element lesser than 100 is:- 190569291
More C++ Programs:
