View source for 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 

<math>
0 \leq a_j < m_j \qquad for 1 \leq j \leq n
</math>

where upper limits might be different for different components <math>(a_1, a_2, \dots, a_n)</math>

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

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

==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.

<pre>
# 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
</pre>

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

<pre>
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)
</pre>