AOCP/Generating Permutations and Tuples

Algorithms for generating all permutations and tuples

Add-One Mixed Radix Generation Agorithm

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 {\mbox{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}\}$

Then 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 M

Algorithm M = mixed radix generation 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)

Gray Binary Code Generation Algorithm

Gray binary code provides an alternative way to generate permutations in non-lexicographic order. In particular, it produces permutations such that each permutation changes only one bit. For example, for n=4, we have 0000, 0001, 0011, 0010, 0111, 0101, 0100, etc.

These are important for converting between analog and digital.

Recurrence Relation

Let $\Gamma _{n}$ represent a gray binary sequence of n-bit strings. Then $\Gamma _{n}$ can be defined recursively by the rules:

$\Gamma _{0}=\epsilon$

$\Gamma _{n+1}=0\Gamma _{n},1\Gamma _{n}^{R}$

where epsilon denotes the empty string, $0\Gamma _{n}$ means the string $\Gamma _{n}$ prefixed with 0, and $1\Gamma _{n}^{R}$ denotes teh sequence $\Gamma _{n}$ in reverse order with 1 prefixed to the string

The last string of $\Gamma _{n}$ equals the first string of $\Gamma _{n}^{R}$ so exactly one bit changes each step.

Alternative Formulation

Alternatively, we can define the sequence by giving an explicit formula to individual elements at various positions in the string.

For example:

$\Gamma _{n}=g(0),g(1),\dots ,g(2^{n}-1)$

This gives an explicit formula for individual elements g(k)

Then the infinite sequence

$\Gamma _{\infty }=g(0),g(1),g(2),g(3),g(4),\dots$

$\Gamma _{\infty }=(0)_{2},(1)_{2},(11)_{2},(10)_{2},(110)_{2},$

Is a permutation of all nonnegative integers. Thus, $\Gamma _{n}$ consists of the first 2^n elements of $\Gamma _{\infty }$ converted to n-bit strings by inserting 0s at left, if necessary.

Baudot Code

Baudot is a telegraph machine that uses 5 bits to represent each letter. The baudot telegraph machine uses $\Gamma _{5}$ gray code.

Chinese ring puzzle

Also known as tiring irons. The challenge is to remove rings from bar, but rings are interlocked in such a way that only two moves are possible:

• Rightmost ring can be removed or replaced
• Any other ring can be removed or replaced if the ring to its right is on the bar and all rings to the right of that one are off the bar.

The state of the puzzle can be represented with binary notation, 1 means ring is on the bar and 0 means ring is off the bar

Algorithm G

Algorithm G = gray binary generation algorithm

This algorithm visits all binary tuples $(a_{n-1},a_{n-2},\dots ,a_{1},a_{0})$

Start with $(0,0,\dots ,0,0)$ and change one bit at a time

# Initialize
set a_j <- 0 for 0 <= j < n
set a_infty <- 0


# Visit
visit the n-tuple (a_{n-1}, ..., a_1, a_0)


# Change Parity
set a_infty <- 1 - a_infty


# Choose j
if a_infty = 1:
	set j <- 0
else:
	let j >= 1 be minimum such that a_{j-1} = 1
	after kth time performing this step, j = rho(k)
	(rho is the ruler function)


# Complement Coordinate j
if j = n:
	terminate
else:
	a_j <- 1 - a_j
	return to Visit step