Section 4.4 Permutations and Combinations
285
algoRitHm Combination Generator
CombGenerator(integer n ≥ 2, integer r ≥ 1)
//generates in lexicographical order all combinations
//of r integers from the set {1, …, n}
Local variables:
integers i, j
//indices of combination elements
integer k
//for loop counter
integer max
//maximum allowable value for a digit
integers d 1 , d 2 , …, d r
//left to right elements of a combination
//create and write out smallest combination
for k = 1 to r do
d k = k
end for
write d 1 d 2 … d r
//create and write out remaining combinations
for k = 2 to C(n, r) do
//look right to left for first non-max value
max = n
i = r
while d i = max do //look left
i = i − 1
max = max − 1
end while
//now d i < max, need to increment d i
d i = d i + 1
//reset values right of d i
for j = i + 1 to r do
d j = d j−1 + 1
end for
write d 1 d 2 …d r
end for
end function CombGenerator
PraCtiCe 38 Using this algorithm, find the next combination of five items from {1, … , 9} after 24589. ■