Cool

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

String Permutations

AOCP/Combinatorics

AOCP/Multinomial Coefficients