[Haskell-cafe] Parity of the number of inversions of a permutation

[William Lee Irwin III]

On Wed, Mar 09, 2005 at 12:42:09PM +0100, Henning Thielemann wrote:
> 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'm 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

That's not a permutation, that's a cycle. Permutations are sets of
disjoint cycles (which commute).


-- wli