In today’s Programming Praxis exercise we have to generate all the lexicographic permutations of a list. Let’s get started, shall we?

Some imports:

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

We’re going to be taking a different approach than the Scheme solution, which relies on explicit element swapping. We annotate each element of the list with how many elements are bigger than it. Next, we generate all the permutations of the sequence (not in lexicographic order). We then sort the permutations based on the annotations, reversing them because the most significant number is on the right. Because the biggest element will have an annotation of 0 and the rest are all higher, this results in a lexicographic ordering.

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]

And of course a test to show that our alternative approach is working correctly:

main :: IO ()
main = do print $ perms (<) [1,1]
print $ perms (<) [1,2,3,4]

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, Haskell, kata, lexicographic, permutations, praxis, programming

This entry was posted on March 9, 2010 at 10:20 am and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply