## Lexicographic Permutations

### March 9, 2010

Edsger Dijkstra, in his book *A Discipline of Programming*, describes a function that, given a list of elements and a function that returns a total ordering of those elements, produces the next lexicographic permutation of the list; for instance, the permutations of the list (1 2 3 4) in lexicographic order are (1 2 3 4) (2 1 3 4) (1 3 2 4) (3 1 2 4) (2 3 1 4) (3 2 1 4) (1 2 4 3) (2 1 4 3) (1 4 2 3) (4 1 2 3) (2 4 1 3) (4 2 1 3) (1 3 4 2) (3 1 4 2) (1 4 3 2) (4 1 3 2) (3 4 1 2) (4 3 1 2) (2 3 4 1) (3 2 4 1) (2 4 3 1) (4 2 3 1) (3 4 2 1) (4 3 2 1). With the least significant item in the list at the head, the next greater element than (1 2 3 4) is (2 1 3 4), since the most significant tail of the list doesn’t change, and the next greater permutation differs in the least significant elements. To make a greater permutation, some element of the list must be replaced by a larger element to its left; to make the next permutation, the replacement must happen as far to the left as possible, in the least significant position, and the replacing element must be as small as possible.

Your task is to write functions that return the next lexicographic permutation and a list of all permutations of a list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

[…] Praxis – Lexicographic Permutations By Remco Niemeijer In today’s Programming Praxis exercise we have to generate all the lexicographic permutations of a list. […]

My Haskell solution (see http://bonsaicode.wordpress.com/2010/03/09/programming-praxis-lexicographic-permutations/ for a version with comments):

Interesting. My implementation (http://blog.jeffbergman.com/2010/03/09/permutation-generation-in-f-sharp/) was solving a slightly different problem in that I am printing all permutations of all combinations of elements in the list in lexicographic order. For instance, for the list (1,2,3) I print all permutations of the lists (1), (1,2), (1,3), (2,3), and (1,2,3).

In lexicogrphic order, isn’t (1,2,3,4) followed by (1,2,4,3)?

Anyway, my python version of a generator that returns successive permutations in order.

As explained in the next sentence, the lexicographic order runs from right-to-left, rather than left-to-right, because it is easier when using lists to work at the head of the list, which must be the end (tail) of the permutation.

Here is mine: http://codepad.org/QEWvFfu5

Far from the beauty of Knuth version implemented here by Mike but it was my first time to attempt to resolve such problem.