Assignment 4

---

[ Submission site  |  Show solution  |  Hide solution ]

---

This assignment is a continuation of Assignment 3. In this assignment you are asked to print all partitions of a positive integer. (In the earlier assignment you are asked to report only the count of partitions.) Store in an array all summands chosen so far. A recursive call is made after a new summand is chosen. Append this summand to the array and pass the appended array to the recursive call. When the recursion ends (i.e., the balance becomes zero), print the summand stored in the array one by one from beginning to end.

Part 1 [Credit: 70%]

Write a function that prints all partitions of a positive integer n.

Part 2 [Credit: 20%]

Write a function that prints all partitions of a positive integer n without repeating summands.

Part 3 [Credit: 10%]

Write a function that prints all partitions of a positive integer n having odd numbers of summands.

Note: Make a copy of your program for assignment 3 and modify the copy.

Report the output of your program on the following values of n.

    6
    8
   10
   12
   14

Sample output

   Enter n: 5
   ****** Part 1: All possible partitions
   Total count = 7
   1+1+1+1+1
   1+1+1+2
   1+1+3
   1+2+2
   1+4
   2+3
   5
   ****** Part 2: Partitions without repetitions
   Total count = 3
   1+4
   2+3
   5
   ****** Part 3: Partitions into odd number of parts
   Total count = 4
   1+1+1+1+1
   1+1+3
   1+2+2
   5

---

Solution

   #include <stdio.h>

   void printP ( unsigned long A[] , unsigned long t )
   {
      unsigned long i;

      if (t) {
         printf("%lu", A[0]);
         for (i=1; i<t; ++i) printf("+%lu", A[i]);
      }
      printf("\n");
   }

   unsigned long genP ( unsigned long n , unsigned long m ,
                        unsigned long A[] , unsigned long t )
   /* n stores the remaining balance, m stores the maximum choice so far,
      A[] stores the choices made so far, and t stores the count of choices
      made so far, i.e., the size of A[]. */
   {
      unsigned long i, s;

      if (n == 0) {                     /* if the balance is 0 */
         printP(A,t);                   /* print the summands */
         return 1;
      }
      s = 0;
      for (i = m; i <= n; ++i) {        /* for each next choice i */
         A[t] = i;                      /* store the choice in A */
         s += genP(n-i,i,A,t+1);        /* recursive call */
      }
      return s;
   }

   unsigned long genPNoRep ( unsigned long n , unsigned long m ,
                             unsigned long A[] , unsigned long t )
   /* n stores the remaining balance, m stores the maximum choice so far,
      A[] stores the choices made so far, and t stores the count of choices
      made so far, i.e., the size of A[]. */
   {
      unsigned long i, s;

      if (n == 0) {                     /* if the balance is 0 */
         printP(A,t);                   /* print the summands */
         return 1;
      }
      s = 0;
      for (i = m; i <= n; ++i) {        /* for each next choice i */
         A[t] = i;                      /* store the choice in A */
         s += genPNoRep(n-i,i+1,A,t+1); /* recursive call */
      }
      return s;
   }

   unsigned long genPOdd ( unsigned long n , unsigned long m ,
                           unsigned long A[] , unsigned long t )
   /* n stores the remaining balance, m stores the maximum choice so far,
      A[] stores the choices made so far, and t stores the count of choices
      made so far, i.e., the size of A[]. */
   {
      unsigned long i, s;

      if (n == 0) {                     /* if the balance is 0 */
         if (t % 2) {                   /* if the number of summands is odd */
            printP(A,t);                /* print the summands */
            return 1;
         }
         return 0;
      }
      s = 0;
      for (i = m; i <= n; ++i) {        /* for each next choice i */
         A[t] = i;                      /* store the choice in A */
         s += genPOdd(n-i,i,A,t+1);     /* recursive call */
      }
      return s;
   }

   int main ()
   {
      unsigned long n, cnt;
      unsigned long A[100];

      printf("\n*********************************************************\n");
      printf("Enter n: "); scanf("%lu", &n); printf("%lu\n", n);

      printf("\nPART 1: All partitions\n");
      cnt = genP(n,1,A,0);
      printf("Total count = %lu\n", cnt);

      printf("\nPART 2: Partitions without repetitions\n");
      cnt = genPNoRep(n,1,A,0);
      printf("Total count = %lu\n", cnt);

      printf("\nPART 3: Partitions with odd numbers of summands\n");
      cnt = genPOdd(n,1,A,0);
      printf("Total count = %lu\n", cnt);
   }

Output

---

[ Submission site  |  Show solution  |  Hide solution ]

---

Back  |  Home