ABSTRACT
The previous two chapters explained how to obtain the formula for partitioning integers and also how to write a C program that implements the formula. This chapter explains how to print the partitions and also introduces some variations on the problem. The following program prints the partitions for an integer that is specified on the command line:
// partition.c1
#include <stdio.h>2 #include <stdlib.h>3 #include <string.h>4 void printPartition( int * arr , int length)5 {6
int ind;7 for (ind = 0; ind < length - 1; ind ++)8
{9
printf("%d + ", arr[ind]);10
}11
printf("%d\n", arr[length - 1]);12
}13
void partition( int * arr , int ind , int left)15 {16
int val;17 i f (left == 0)18
{19
printPartition(arr , ind);20
return; // not necessary21 }22
for (val = 1; val <= left; val ++)23 {24
arr[ind] = val;25
partition(arr , ind + 1, left - val);26
}27
}28
i f (argc != 2)32 {33
return EXIT_FAILURE;34 }35
int n = ( int ) strtol(argv[1], NULL , 10);36 i f (n <= 0)37
{38
return EXIT_FAILURE;39 }40
int * arr;41 arr = malloc( s i z eo f ( int ) * n);42 partition(arr , 0, n);43
free (arr);44
return EXIT_SUCCESS;45 }46
The partition function is the core of this program. This function takes three arguments: 1. arr is an integer pointer. It is an array that stores the numbers used in a given
partition. 2. ind is an integer. It is an index of the array. The value indicates where the next
element will be written. It also gives the length of the partition so far. 3. left is an integer. It is the remaining value to be partitioned.
