Chapter 14
Integer Partition
14.1 Stack and Heap Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
14.2 Trace Recursive Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
14.3 Generating Partitions with Restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
14.3.1 Using Odd Numbers Only . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
14.3.2 Using Sequences of Increasing Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
14.3.3 Using Alternating Odd and Even Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
14.3.4 Using gprof and gcov to Identify Performance Bottlenecks . . . . . . . . . . 216
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:
// part ition . c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
#in clude < string .h >4
void print Partit ion ( in t * 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
14
void partition ( i n t * arr , i nt ind , i nt left )15
{16
int val ;17
i f ( left == 0)18
{19
prin t Partit ion ( arr , ind );20
return ; // not n ecessary21
}22
for ( val = 1; val <= left ; val ++)23
{24
arr [ ind ] = val ;25
partition ( arr , ind + 1 , left - val ) ;26
}27
}28
29
201
202 Intermediate C Programming
int main ( i n t argc , char * argv [])30
{31
i f ( argc != 2)32
{33
return EXIT _FAILUR E ;34
}35
int n = ( i n t ) strtol ( argv [1] , NULL , 10) ;36
i f (n <= 0)37
{38
return EXIT _FAILUR E ;39
}40
int * arr ;41
arr = malloc ( s i z e o f ( i nt ) * n) ;42
partition ( arr , 0, n );43
free ( arr );44
return EXIT _SUCCES S ;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.
The return at line 21 is unnecessary. When left is zero, the function will not enter the
for loop. Adding this return makes the program easier to read.
When main calls partition, ind is zero—the index of the first element of the array. The
value left is the remaining value to be partitioned. Even though this program is short, it
reviews many important concepts explained earlier. Thus, it is worth explaining in detail.
14.1 Stack and Heap Memory
Suppose the value of n is 4. The following table shows the stack and heap memory after
running line 42 and before line 43. The table assumes that each integer occupies 4 bytes
(sizeof(int) is 4).
Frame Symbol Address Value
main
arr 101 10000
n 100 4
(a) Stack Memory
Symbol Address Value
arr[3] 10012 garbage
arr[2] 10008 garbage
arr[1] 10004 garbage
arr[0] 10000 garbage
(b) Heap Memory
Integer Partition 203
This is the call stack and the heap memory after entering the function partition. RL
means return location.
Frame Symbol Address Value
partition
val 106 garbage
left 105 4
ind 104 0
arr 103 10000
RL 102 line 44
main
arr 101 10000
n 100 4
(a) Stack Memory
Symbol Address Value
arr[3] 10012 garbage
arr[2] 10008 garbage
arr[1] 10004 garbage
arr[0] 10000 garbage
(b) Heap Memory
The value of left is not zero and the terminating condition at line 18 is false. The
function continues to the for loop at lines 23–27. In this for loop, we let val iterate from
1 to left. These are all the possible values that can be used. The value of val starts at 1.
Thus line 25 first assigns 1 to arr[0].
Frame Symbol Address Value
partition
val 106 1
left 105 4
ind 104 0
arr 103 10000
RL 102 line 44
main
arr 101 10000
n 100 4
(a) Stack Memory
Symbol Address Value
arr[3] 10012 garbage
arr[2] 10008 garbage
arr[1] 10004 garbage
arr[0] 10000 garbage → 1
(b) Heap Memory
The function then calls itself at line 26. Please notice the values of ind and left. The
index has changed from 0 to 1 because line 26 uses ind + 1. This is the next position in arr
for the next value. In the recursive call, the function needs to partition 3 because left - val
is 3. That is, we wrote 1 to position 0, and now we want to partition n − 1 = 4 − 1 = 3 into
the remaining portion of arr. Please pay attention to the top frame of the call stack.
204 Intermediate C Programming
Frame Symbol Address Value
partition
val 111 garbage
left 110 3
ind 109 1
arr 108 10000
RL 107 line 27
partition
val 106 1
left 105 4
ind 104 0
arr 103 10000
RL 102 line 44
main
arr 101 10000
n 100 4
(a) Stack Memory.
Symbol Address Value
arr[3] 10012 garbage
arr[2] 10008 garbage
arr[1] 10004 garbage
arr[0] 10000 garbage → 1
(b) Heap Memory
The for loop starts with val equal to 1. Line 25 assigns 1 to arr[1] because ind is 1.
Frame Symbol Address Value
partition
val 111 1
left 110 3
ind 109 1
arr 108 10000
RL 107 line 27
partition
val 106 1
left 105 4
ind 104 0
arr 103 10000
RL 102 line 44
main
arr 101 10000
n 100 4
(a) Stack Memory
Symbol Address Value
arr[3] 10012 garbage
arr[2] 10008 garbage
arr[1] 10004 garbage → 1
arr[0] 10000 garbage → 1
(b) Heap Memory
The function calls itself again at line 26.
Integer Partition 205
Frame Symbol Address Value
partition
val 116 garbage
left 115 2
ind 114 2
arr 113 10000
RL 112 line 27
partition
val 111 1
left 110 3
ind 109 1
arr 108 10000
RL 107 line 27
partition
val 106 1
left 105 4
ind 104 0
arr 103 10000
RL 102 line 44
main
arr 101 10000
n 100 4
(a) Stack Memory
Symbol Address Value
arr[3] 10012 garbage
arr[2] 10008 garbage
arr[1] 10004 garbage → 1
arr[0] 10000 garbage → 1
(b) Heap Memory
Continuing these steps, left eventually decreases and becomes zero.
Frame Symbol Address Value
partition
val 126 garbage
left 125 0
ind 124 4
arr 123 10000
RL 122 line 27
partition
val 121 1
left 120 1
ind 119 3
arr 118 10000
RL 117 line 27
partition
val 116 1
left 115 2
ind 114 2
arr 113 10000
RL 112 line 27
partition
val 111 1
left 110 3
ind 109 1
arr 108 10000
RL 107 line 27
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset