## 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

### 6 Responses to “Lexicographic Permutations”

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

2. Remco Niemeijer said

```import Data.List
import qualified Data.List.Key as K

perms :: (a -> a -> Bool) -> [a] -> [[a]]
perms cmp xs = map fst . K.sort (reverse . snd) . map unzip \$
permutations [(x, length \$ filter (cmp x) xs) | x <- xs]
```
3. Jeff said

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).

4. Mike said

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.

```def permutations_of( seq ):
yield seq
seqlen = len(seq)
while True:
j = seqlen - 2
while j >= 0 and seq[j] >= seq[j+1]:
j -= 1

if j < 0: break

i= seqlen - 1
while i > j and seq[i] < seq[j]:
i -= 1

seq[j],seq[i] = seq[i],seq[j]
seq[j+1:] = seq[-1:j:-1]
yield seq
```
5. programmingpraxis said

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.

6. Valentin said