Integer Partition 211
FIGURE 14.1: Graphical illustration of f1 calls f2.
void f1 ()1
{2
f2 () ;3
f3 () ;4
}5
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
{2
f2 () ;3
f3 () ;4
}5
void f2 ()6
{7
f3 () ;8
}9
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
{2
int count ;3
for ( count = 1; count < 4; count ++)4
{5
f2 () ;6
}7
f3 () ;8
212 Intermediate C Programming
}9
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
{2
int val ;3
for ( val = 1; val <= left ; val ++)4
{5
arr [ ind ] = val ;6
partition ( arr , ind + 1 , left - val ) ;7
}8
}9
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 different 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 satisfied 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 modified as follows:
void print Partit ion ( in t * arr , int length )1
{2
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
{7
i f (( arr [ ind ] % 2) == 0)8
{9
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
{2
int ind ;3
for ( ind = 0; ind < length - 1; ind ++)4
{5
i f ( arr [ ind ] >= arr [ ind + 1]) // not i ncreasing6
{7
return ;8
}9
}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 inefficient because many invalid partitions have al-
ready been generated. Instead, a more efficient 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 “filtered” 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
{2
int val ;3
i f ( left == 0)4
{5
prin t Partit ion ( arr , ind );6
return ;7
}8
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
{2
int val ;3
i f ( left == 0)4
{5
prin t Partit ion ( arr , ind );6
return ;7
}8
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
first 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
{2
int val ;3
i f ( left == 0)4
{5
prin t Partit ion ( arr , ind );6
return ;7
}8
for ( val = 1; val <= left ; val ++)9
{10
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.