[Haskell-cafe] Parity of the number of inversions of a permutation
Henning Thielemann
lemming at henning-thielemann.de
Wed Mar 9 06:42:09 EST 2005
I think it is a quite popular problem. I have a permutation and I want to
count how often a big number is left from a smaller one. More precisely
I'm interested in whether this number is even or odd. That's for instance
the criterion to decide whether Lloyd's shuffle puzzle is solvable or not.
Example:
1 4 3 2
I can choose six pairs (respecting the order) of numbers out of it, namely
(1,4) (1,3) (1,2) (4,3) (4,2) (3,2), where in the last three pairs the
first member is greater than the second one. Thus I have 3 inversions and
an odd parity.
I' searching for a function which sorts the numbers and determines the
parity of the number of inversions. I assume that there are elegant and
fast algorithms for this problem (n * log n time steps), e.g. a merge sort
algorithm. A brute force solution with quadratic time consumption is
countInversions :: (Ord a) => [a] -> Int
countInversions = sum . map (\(x:xs) -> length (filter (x>) xs)) . init . tails
More information about the Haskell-Cafe
mailing list