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.

Note that the "visit" action is where we hand things off to the consumer (whoever is asking for permutations, to do whatever they are going to do).

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)