Intermediate C Programming

Integer Partition 211

FIGURE 14.1: Graphical illustration of f1 calls f2.

void f1 ()1

f2 () ;3

f3 () ;4

FIGURE 14.2: Graphical illustration of f1 calls f2 and f3.

This is the third example and the calling relation is shown in Fig. 14.3.

void f1 ()1

f2 () ;3

f3 () ;4

void f2 ()6

f3 () ;8

FIGURE 14.3: Graphical illustration of f1 calls f2 and f3; f2 also calls f3.

Here we add a loop to the function f1 and Fig. 14.4 shows the relation.

void f1 ()1

int count ;3

for ( count = 1; count < 4; count ++)4

f2 () ;6

f3 () ;8

212 Intermediate C Programming

void f2 ()10

{11

f3 () ;12

}13

FIGURE 14.4: Graphical illustration of f1 calls f2 in a loop and f3 outside a loop; f2

calls f3.

Next, let’s consider the skeleton of the partition function:

void partition ( i n t * arr , i nt ind , i nt left )1

int val ;3

for ( val = 1; val <= left ; val ++)4

arr [ ind ] = val ;6

partition ( arr , ind + 1 , left - val ) ;7

Fig. 14.5 illustrates the calling relation.

FIGURE 14.5: Graphical illustration of partition when the initial value of left is 3.

When left is 3, then val can be 1, 2, or 3.

1. When val is 1, left-val is 2. Thus, partition(arr, 1, 2) is called.

2. When val is 2, left-val is 1. Thus, partition(arr, 1, 1) is called.

3. When val is 3, left-val is 0. Thus, partition(arr, 1, 0) is called.

When left is 2, val can be 1 or 2. The calling relationship is illustrated in Fig. 14.6 and

Fig. 14.7.

The call tree is a diﬀerent way to help understand the calling relation. It is a higher

level representation than the call stack because each call is represented by arguments and

we do not need to examine all of the addresses and values used in each call.

Integer Partition 213

FIGURE 14.6: Graphical illustration of partition when the value of left is 2.

FIGURE 14.7: Graphical illustration of partition when the value of left is 1.

14.3 Generating Partitions with Restrictions

The program at the beginning of this chapter prints all possible partitions. This section

explains how to change the program such that it generates partitions with restrictions, for

example, partitioning with odd numbers or using sequences of increasing numbers. One

simple solution is to check whether the restrictions have been satisﬁed before printing.

Thus, in the base case, before printing anything, the function checks whether this partition

is valid under the restriction. For example, if we are partitioning with odd numbers only,

printPartition can be modiﬁed as follows:

void print Partit ion ( in t * arr , int length )1

int ind ;3

// check whether any number is even4

// if an even number is used , do not print a n ything5

for ( ind = 0; ind < length ; ind ++)6

214 Intermediate C Programming

i f (( arr [ ind ] % 2) == 0)8

return ;10

}11

}12

for ( ind = 0; ind < length - 1; ind ++)13

{14

printf (" %d + " , arr [ ind ]) ;15

}16

printf (" %d\ n" , arr [ length - 1]) ;17

}18

To check whether the numbers form an increasing sequence:

void print Partit ion ( in t * arr , int length )1

int ind ;3

for ( ind = 0; ind < length - 1; ind ++)4

i f ( arr [ ind ] >= arr [ ind + 1]) // not i ncreasing6

return ;8

}10

for ( ind = 0; ind < length - 1; ind ++)11

{12

printf (" %d + " , arr [ ind ]) ;13

}14

printf (" %d\ n" , arr [ length - 1]) ;15

}16

However, checking before printing is ineﬃcient because many invalid partitions have al-

ready been generated. Instead, a more eﬃcient solution does not generate invalid partitions.

This section explains how to generate valid partitions satisfying one of the following restric-

tions: (i) using odd numbers only, (ii) using increasing numbers, and (iii) using alternating

odd and even numbers.

14.3.1 Using Odd Numbers Only

The function partition generates only partitions that meet the criteria. It is thus much

faster than an approach where all partitions are generated and then “ﬁltered” before being

printed. If only odd numbers are used, val can be an odd number only.

void partition ( i n t * arr , i nt ind , i nt left )1

int val ;3

i f ( left == 0)4

prin t Partit ion ( arr , ind );6

return ;7

for ( val = 1; val <= left ; val += 2) // odd n u mbers only9

Integer Partition 215

{10

arr [ ind ] = val ;11

partition ( arr , ind + 1 , left - val ) ;12

}13

}14

This will generate fewer partitions and all of them are valid.

14.3.2 Using Sequences of Increasing Numbers

To generate partitions using increasing numbers, the smallest value of val must be

greater than the most recently used value stored in arr. However, if ind is zero, then no

previously used value is stored in arr, and val can start from one.

void partition ( i n t * arr , i nt ind , i nt left )1

int val ;3

i f ( left == 0)4

prin t Partit ion ( arr , ind );6

return ;7

int min = 1;9

i f ( ind != 0)10

{11

min = arr [ ind - 1] + 1;12

}13

for ( val = min ; val <= left ; val ++)14

{15

arr [ ind ] = val ;16

partition ( arr , ind + 1 , left - val ) ;17

}18

}19

14.3.3 Using Alternating Odd and Even Numbers

To generate alternating odd and even numbers, the function must check whether ind

is zero. If it is zero, val can be either odd or even, because val is being written into the

ﬁrst position of the partition. If ind is greater than zero, then the function needs to check

arr[ind - 1]. If arr[ind - 1] is odd, then val must be an even number. If arr[ind - 1]

is even, then val must be an odd number. This is checked in line 18.

void partition ( i n t * arr , i nt ind , i nt left )1

int val ;3

i f ( left == 0)4

prin t Partit ion ( arr , ind );6

return ;7

for ( val = 1; val <= left ; val ++)9

{10

Previous Chapter

14. Integer Partition (2/5)

Next Chapter

14. Integer Partition (4/5)

Table of Contents for Intermediate C Programming

Table of Contents for
Intermediate C Programming