AOCP/Generating Permutations and Tuples

Algorithms for generating all permutations and tuples

Binary string permutations

Knuth starts simple - with binary strings.

Suppose we want to generate all 2^n binary strings of length n. How can we do that?

It is surprisingly easy - just start at 0, and keep adding 1 until you get to 11...11 (where there are n 1s). That's 2^n-1.

Decimal string permutations

If we have more than two objects, we can use the same approach as above. For example, suppose we have all ten decimal numbers, 0 through 9, and we want to generate all strings of length n that are permutations of these digits. There are 10^n such strings.

We can start at 0 base 10, and count up to 99...99 base 10 (where we start with n 0's and keep going until we have n 9's). That's 10^n-1.

Arbitrary string permutations

Suppose we want to run through all cases in which

$ 0 \leq a_j < m_j \qquad for 1 \leq j \leq n $

where upper limits might be different for different components $ (a_1, a_2, \dots, a_n) $

This is a multiset problem, where we have the multiset $ \{ m_1 \cdot a_1, m_2 \cdot a_2, \dots, m_n \cdot a_n \} $

Thien the task is essentially the same as repeatedly adding unity to the number $ \left[ a_1, a_2, a_3, \dots, a_n \right] $ in the mixed-radix number system $ \left[ m_1, m_2, \dots, m_n \right] $

Algorithm

Algorithm for mixed-radix generation of permutations: this algorithm is a generalization of the "sequentially add one to the given number" approach

This algorithm visits all n-tuples by repeatedly adding 1 to the mixed-radix number until overflow occurs

Auxiliary variables a0 and m0 are introduced as well.

# Initialization
set a_j <- 0 for 0 <= j <= n
set m_0 <- 0


# Visit
visit the n-tuple (a_1, ..., a_n) 
pass off control to the consumer


# Prepare To Add One
set j <- n


# Carry If Necessary
if a_j = m_j - 1, set a_j <- 0, j <- j-1
Repeat this step


# Increase Unless Done
if j=0: 
	terminate
else: 
	a_j <- a_j + 1
return to Visit step

Note that if the number of slots (n) is small, we can write it out using nested for loops:

for a_1 in range 0 to (m_1 - 1):
	for a_2 in range 0 to (m_2 - 1):
		for a_3 in range 0 to (m_3 - 1):
			for a_4 in range 0 to (m_4 - 1):
				visit the n-tuple (a_1, a_2, a_3, a_4)