From charlesreid1

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

Cool-Lexicographic Order

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


  • 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 ( != null or afteri.value < head.value) do:
    if ( != null and i.value >=
        beforek <- afteri
        beforek <- i
    k <- <- <- head
    if (k.value < head.value):
        i <- k
    afteri <-
    head <- k

Related Pages

String Permutations


AOCP/Multinomial Coefficients