Page 458 - Discrete Mathematics and Its Applications

6.6 Generating Permutations and Combinations 437

Generating Combinations

How can we generate all the combinations of the elements of a finite set? Because a combination
is just a subset, we can use the correspondence between subsets of {a 1 ,a 2 ,...,a n } and bit strings
of length n.
Recall that the bit string corresponding to a subset hasa1in position k if a k is in the subset,
andhasa0in this position if a k is not in the subset. If all the bit strings of length n can be listed,
then by the correspondence between subsets and bit strings, a list of all the subsets is obtained.
Recall that a bit string of length n is also the binary expansion of an integer between 0 and
n
n
2 − 1. The 2 bit strings can be listed in order of their increasing size as integers in their binary
expansions. To produce all binary expansions of length n, start with the bit string 000 ... 00, with
n zeros. Then, successively find the next expansion until the bit string 111 ... 11 is obtained. At
each stage the next binary expansion is found by locating the first position from the right that is
not a 1, then changing all the 1s to the right of this position to 0s and making this first 0 (from
the right) a 1.

EXAMPLE 4 Find the next bit string after 10 0010 0111.

Solution: The first bit from the right that is nota1isthe fourth bit from the right. Change
this bit to a 1 and change all the following bits to 0s. This produces the next larger bit string,
10 0010 1000. ▲

The procedure for producing the next larger bit string after b n−1 b n−2 ...b 1 b 0 is given as
Algorithm 2.

ALGORITHM 2 Generating the Next Larger Bit String.

procedure next bit string(b n−1 b n−2 ...b 1 b 0 : bit string not equal to 11...11)
i := 0
while b i = 1
b i := 0
i := i + 1
b i := 1
{b n−1 b n−2 ...b 1 b 0 is now the next bit string}

Next, an algorithm for generating the r-combinations of the set {1, 2, 3,...,n} will be
given. An r-combination can be represented by a sequence containing the elements in the
subset in increasing order. The r-combinations can be listed using lexicographic order on
these sequences. In this lexicographic ordering, the first r-combination is {1, 2,...,r − 1,r}
and the last r-combination is {n − r + 1,n − r + 2,...,n − 1,n}. The next r-combination
after a 1 a 2 ··· a r can be obtained in the following way: First, locate the last element a i in the
sequence such that a i = n − r + i. Then, replace a i with a i + 1 and a j with a i + j − i + 1,
for j = i + 1,i + 2,...,r. It is left for the reader to show that this produces the next larger
r-combination in lexicographic order. This procedure is illustrated with Example 5.

EXAMPLE 5 Find the next larger 4-combination of the set {1, 2, 3, 4, 5, 6} after {1, 2, 5, 6}.
Solution: The last term among the terms a i with a 1 = 1, a 2 = 2, a 3 = 5, and a 4 = 6 such that
a i = 6 − 4 + i is a 2 = 2. To obtain the next larger 4-combination, increment a 2 by 1 to obtain
a 2 = 3. Then set a 3 = 3 + 1 = 4 and a 4 = 3 + 2 = 5. Hence the next larger 4-combination is
{1, 3, 4, 5}. ▲