C Program to Perform Integer Partition for a Specific Case

This C program perform integer partition for a specific case.

This algorithm partitions an integer into numbers which sum up to form the original number.

Here is the source code of the C program to perform integer partition. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct {
  4.      int first;
  5.      int n;
  6.      int level;
  7. } Call;
  8.  
  9.  
  10. void print(int n, int * a) {
  11.      int i ;
  12.      for (i = 0; i <= n; i++) {
  13.           printf("%d", a[i]);
  14.      }
  15.      printf("\n");
  16. }
  17.  
  18.  
  19. void integerPartition(int n, int * a){
  20.      int first;
  21.      int i;
  22.      int top = 0;
  23.      int level = 0;
  24.      Call * stack = (Call * ) malloc (sizeof(Call) * 1000);
  25.      stack[0].first = -1;
  26.      stack[0].n = n;
  27.      stack[0].level = level;
  28.      while (top >= 0){
  29.           first = stack[top].first;
  30.           n = stack[top].n;
  31.           level = stack[top].level;
  32.           if (n >= 1) {
  33.                if (first == - 1) {
  34.                     a[level] = n;
  35.                     print(level, a);
  36.                     first = (level == 0) ? 1 : a[level-1];
  37.                     i = first;
  38.                } else {
  39.                     i = first;
  40.                     i++;
  41.                }
  42.                if (i <= n / 2) {
  43.                     a[level] = i;
  44.                     stack[top].first = i;
  45.                     top++;
  46.                     stack[top].first = -1;
  47.                     stack[top].n = n - i;
  48.                     stack[top].level = level + 1;
  49.           } else {
  50.                top--;
  51.           }
  52.      } else {
  53.      top --;
  54.      }
  55. }
  56. }
  57.  
  58. int main(){
  59.     int n = 4;
  60.     int * a = (int * ) malloc(sizeof(int) * n);
  61.     printf("\nThe integer partition for %d is :\n", n);
  62.     integerPartition (n, a);
  63.     return(0);
  64. }

$ gcc integer_partition.c -o integer_partition
$ ./integer_partition
The integer partition for 4 is :
4
13
112
1111
22

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

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

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.