C Program to Perform the Unique Factorization of a Given Number

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.

  1. #include<stdio.h>
  2. void printarray(int p[], int n)
  3. {
  4.     int i;
  5.     for ( i = 0; i < n; i++)
  6.        printf("%d ", p[i]);
  7.     printf("\n");
  8. }
  9.  
  10. void partition(int n)
  11. {
  12.     int p[n]; // An array to store a partition
  13.     int k = 0;  // Index of last element in a partition
  14.     p[k] = n;  // Initialize first partition as number itself
  15.     int rem_val;
  16.     // This loop first prints current partition, then generates next
  17.     // partition. The loop stops when the current partition has all 1s
  18.     while (1)
  19.     {
  20.         // print current partition
  21.         printarray(p, k+1);
  22.         rem_val = 0;
  23.         while (k >= 0 && p[k] == 1)
  24.         {
  25.             rem_val += p[k];
  26.             k--;
  27.         }
  28.  
  29.         // if k < 0, all the values are 1 so there are no more partitions
  30.         if (k < 0)  return;
  31.  
  32.         // Decrease the p[k] found above and adjust the rem_val
  33.         p[k]--;
  34.         rem_val++;
  35.  
  36.  
  37.         // If rem_val is more, then the sorted order is violated.  Divide
  38.         // rem_val in different values of size p[k] and copy these values at
  39.         // different positions after p[k]
  40.         while (rem_val > p[k])
  41.         {
  42.             p[k+1] = p[k];
  43.             rem_val = rem_val - p[k];
  44.             k++;
  45.         }
  46.  
  47.         // Copy rem_val to next position and increment position
  48.         p[k+1] = rem_val;
  49.         k++;
  50.     }
  51. }
  52. int main()
  53. {
  54.     int num;
  55.     printf("\nEnter a number to perform integer partition: ");
  56.     scanf("%d", &num);
  57.     partition(num);
  58.     return 0;
  59. }

$ 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.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.