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)
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
if (k.value < head.value):
i <- k
end
afteri <- i.next