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.
Programming Praxis 
[…] 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):
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]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.
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 seqAs 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.