This is a C Program to get all the unique partitions of a given integer such that addition of a partition results an integer. Given a positive integer n, generate all possible unique ways to represent n as sum of positive integers.
Here is the source code of the C program to partition an integer in all possible ways. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<stdio.h>
void printarray(int p[], int n)
{
int i;
for ( i = 0; i < n; i++)
printf("%d ", p[i]);
printf("\n");
}
void partition(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
int rem_val;
// This loop first prints current partition, then generates next
// partition. The loop stops when the current partition has all 1s
while (1)
{
// print current partition
printarray(p, k+1);
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 violated. Divide
// rem_val in different values of size p[k] and 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++;
}
}
int main()
{
int num;
printf("\nEnter a number to perform integer partition: ");
scanf("%d", &num);
partition(num);
return 0;
}
$ gcc partition.c -o partition $ ./partition Enter a number to perform integer partition: 6 5 1 4 2 4 1 1 3 3 3 2 1 3 1 1 1 2 2 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1
Sanfoundry Global Education & Learning Series – 1000 C Programs.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
Here’s the list of Best Books in C Programming, Data Structures and Algorithms.
Next Steps:
- Get Free Certificate of Merit in C Programming
- Participate in C Programming Certification Contest
- Become a Top Ranker in C Programming
- Take C Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Apply for C Internship
- Practice Computer Science MCQs
- Practice BCA MCQs
- Watch Advanced C Programming Videos
- Buy Computer Science Books