7th July 1975

__On a gauntlet thrown by David Gries__.

Freshly arrived from the U.S.A. —they still struggled with the time shift— David Gries and his family paid us a visit a few weeks ago. It was not an occasion for "working together", yet some shoptalk was unavoidable, and David confronted me with the problem how to generate the `n`! permutations of the numbers 0 through `n`-1 such that the transition from one permutation to the next would only involve the swapping of two neighbours. He told me the problem because he had found it a non-trivial task to present an algorithm solving this problem in a convincing manner. He —good boy!— respected my desire not to be told how he had solved the difficulties of presenting his solution, and he granted me the opportunity to think about the problem myself. (He told me, that the problem had been dealt with in the Algorithms Section of the* Comm.ACM*, but at the level of unintelligibility that is characteristic for that Section, and we agreed wholeheartedly that a tradition of clearer presentation of algorithms is most sorely needed.)

__Note__. Those of my readers who would like to try to solve this problem themselves should
stop reading here. (End of Note.)

As the swapping of two neighbours changes the number of inversions —i.e. the number of pairs in the wrong order— by 1 , it is suggested to try to characterize each permutation by its inversions. If we consider an arbitrary permutation of the numbers 0 through `n`-1 , each permutation is uniquely characterized by the values `inv`(`i`) , with 0 ≤ `inv`(`i`) ≤ `i` for 0 ≤ `i` < `n` , where `inv`(`i`) equals the number of numbers < `i` , that are placed at "the wrong side" of `i` ; `inv`(`i`) = the number of inversions between the value `i` and smaller values. (The total number of inversions of the permutation is the sum of all the `inv`(`i`)-values.) That each permutation defines the `inv`(`i`)-values uniquely is obvious; that the `inv`(`i`)-values define the permutation uniquely is also not difficult to see, when we consider the algorithm constructing the permutation from the `inv`(`i`)-values —processing these values in the order of increasing `i` —: this is an algorithm that leaves us no choice.

There is, therefore, a one-to-one correspondence between the `n`! possible `inv`-values and the `n`! permutations, and the question becomes, which modifications of the `inv`-value correspond to a swap of neighbours: each swap of two neighbours changes exactly one `inv`(`i`)-value by one, viz. with `i` = the larger of the two values swapped. The value of `inv`(`i`) is to be increased by one if the swap brings the pair into the wrong order, otherwise it has to be decreased by one.

A feasible sequence of `inv`-values to be generated is now reasonably obvious: it is the generalization of the Grey-code. For `n` = 4 it would begin

0 0 0 0

0 0 0 1

0 0 0 2

0 0 0 3

0 0 1 3

0 0 1 2

0 0 1 1

0 0 1 0

0 0 2 0

0 0 2 1

0 0 2 2

0 0 2 3

0 1 2 3

0 1 2 2

etc.

The rule is as follows: a number is changeable when it may be increased or decreased by one. It may be increased if the sum of the numbers to its left is even and it has not reached its maximum value; it may be decreased if the sum of the numbers to its left is odd and it has not reached its minimum value zero. At each step, always the right-most changeable number is changed.

After having established the value `i` such that `inv`(`i`) has to be changed and, also, whether the value `i` has to be swapped with its left-hand neighbour (because this is a smaller one, `inv`(`i`) has to be increased) or with its right-hand neighbour (a decrease of `inv`(`i`) by one), we have to establish the place `c` in the array, where the element i is positioned; this is given by

`c` = `i` − `inv`(`i`) + (the number of values `j` such that `j` > `i` __and__ `inv`(`j`) = [?]

The reason for this formula: `i` is its original position, `inv`(`i`) is the number of smaller elements to the right of it; we have to add to it the number of larger elements in front of the section with elements ≤ `i` .

In the following program we have given `inv`(0) —which should be constantly 0— the funny value -2; this is just the usual, mean, little coding trick, in order to let the search for the right-most changeable number terminate artificially when there is no more such a number. The value `totinv` records the total number of inversions in the array `a`; the variable `linv` records the sum of the (non-funny) `inv`-values to the left of `inv`(`i`).

begingloconn;privara, inv, ready, totinv; avirintarray:= (0, 0) {a initialized with a(0) = 0}; invvirintarray:= (0, -2) {inv initialized with inv(0) = - 2};doinv.dom ≠ n → a:hiext(inv.dom); inv:hiext(0)od{a(0),..., a(n-1) = 0,..., n-1 and inv(0),...,inv(n-1) = -2, 0,..., readyvirbool := false; totinvvirint := 0;dononready →begingloconn;glovara, inv, ready, totinv;privari, c, linv; printarray (a); ivirint := n - 1; cvirint := 0; linvvirint := totinv - inv(i)doinv(i) = iandeven(linv) → c:= c + 1 ; i:= i - 1 ; linv := linv - inv(i) ▯ inv(i) = 0andodd(linv) → i:= i - 1 ; linv := linv - inv(i)od; c := c + i - inv(i);ifeven(linv)andi ≥ 1 → inv:(i) = inv(i) + 1 ; totinv := totinv + 1; a:swap(c - 1, c) ▯ odd(linv)andi ≥ 1 → inv:(i) = inv(i) - 1 ; totinv := totinv - 1; a:swap(c, c + 1) ▯ i = 0 → ready := truefiendodend

Plataanstraat 5 NL-4565 NUENEN The Netherlands |
prof.dr.Edsger W.Dijkstra Burroughs Research Fellow |