# AOCP/Generating Permutations and Tuples

### From charlesreid1

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

where upper limits might be different for different components

This is a multiset problem, where we have the multiset

Thien the task is essentially the same as repeatedly adding unity to the number in the mixed-radix number system

## 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 represent a gray binary sequence of n-bit strings. Then can be defined recursively by the rules:

where epsilon denotes the empty string, means the string prefixed with 0, and denotes teh sequence in reverse order with 1 prefixed to the string

The last string of equals the first string of 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:

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

Then the infinite sequence

Is a permutation of all nonnegative integers. Thus, consists of the first 2^n elements of 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 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

Start with 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

# Flags

## AOCP

The Art of Computer ProgrammingArt of Computer Programming
Part of the 2017 CS Study Plan.
AOCP/Infinite Series
AOCP/Combinatorics
AOCP/Combinatorial Algorithms
· Template:AOCPFlag · e |

## Combinatorics

Combinatorics
Ordinary generating functions
Enumerating Permutations: String Permutations Generating Permutations: Cool
Longest Increasing Subsequence
· Template:CombinatoricsFlag · e |

## Algorithms

AlgorithmsSeries on Algorithms
Algorithms/Sort Three solid O(n log n) search algorithms: Merge Sort Algorithm Analysis/Merge Sort
Algorithms/Search
Algorithms/Combinatorics
Algorithms/Strings
Algorithm complexity Amortization Algorithm Analysis/Matrix Multiplication
Estimation
Project Euler
· Template:AlgorithmsFlag · e |