Programming Praxis – Lexicographic Permutations

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]

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: