Brandon.Si(mmons)

my code, art and projects

Find a Permutation Given Its Inversion Table

Here is some code I whipped up in response to an interesting problem posted on reddit.com/r/coding/. It was a really interesting algorithm to work out:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import Data.List (sortBy)

-- takes an inversion list and converts it to the list of permuted  
-- elements:  
decode = dec [] . sortBy lowHi . zip [1..] where
    dec as [] = as
    dec as ((a,_):is) = let is' = sortBy lowHi (decrementGT a is)
                         in dec (a:as) is'

-- decrement every inversion number by 1, for every tuple in which  
-- the element is greater than `a`:  
decrementGT a = map (\(a',i) -> (a', if a'>a then i-1 else i) )

-- we sort by the inversion number, low to high. For elements with  
-- the same inversion number, we say that the greater element tuple  
-- should go before a lesser element:  
lowHi (a,i) (a',i')
    | i == i' = if a>a' then LT else GT
    | otherwise = compare i i'

It’s not the prettiest code I’ve written, but it’s pretty straight-forward and concise. Thanks for looking!

Comments