# Cool

### From charlesreid1

## Contents

# Generating permutations in Cool-Lexicographic Order

The task of actually generating all of the permutations of words that contain a certain set of characters is an extremely important one. (Knuth covers this exclusively in Volume 4 Facsimile 2 of his Art of Computer Programming volumes.)

We can generate permutations in several ways:

- lexicographic order, or sorted order
- de Bruijn cycles, where we remove an item from the front and add an item to the rear
- binary reflected Gray code, where we change only a single item at a time
- Cool-lexicographic order (see http://webhome.csc.uvic.ca/~haron/CoolMulti.pdf)

### Cool-Lexicographic Order

This is a nice simple algorithm that implements an iterative, non-recursive, loopless permutation generator.

Algorithm:

- Visits every permutation of integer multiset E
- Call to init(E) creates singly linked list that stores elements of E in non-increasing order
- head, min, and inc point to first, second to last, and last nodes, respectively
- All variables are pointers
- phi is null
- If E = {1,1,2,4}, then first three visit(E) calls will produce the configurations:
- 4 2 1 1
- 1 4 2 1
- 4 1 2 1

Notes on variables:

- head points to first node of current permutation
- i points to ith node of current permutation
- afteri points to the (i+1)st node of current permutation

to apply the prefix shift of length k, the two pointers k and beforek are used:

- k points to the kth node of the current permutation
- beforek points to the (k-1)st node of the current permutation

Note that the visit(head) call denotes a new permutation that has been generated

- visit(head) happens when new permutation pointed to by head
- Represents passing control back to consumer requesting permutations
- Work in init(E) would also be done by consumer

When does the loop stop?

- Condition on loop ensures algorithm continues until it generates tail(E)
- Rather than generating tail(E) as separate case after oop ends, it initializes linked list to tail(E)
- This is the very first permutation visited

Here is the algorithm:

[head, i afteri] <- init(E) visit(head) while (afteri.next != null or afteri.value < head.value) do: if (afteri.next != null and i.value >= afteri.next.value): beforek <- afteri else beforek <- i end k <- beforek.next beforek.next <- k.next k.next <- head if (k.value < head.value): i <- k end afteri <- i.next head <- k visit(head) end

# Related Pages

# Flags

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

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 |