Posts Tagged ‘lexicographic’

Programming Praxis – Lexicographic Permutations

March 9, 2010

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]