[Haskell-cafe] Parity of the number of inversions of a permutation
William Lee Irwin III
wli at holomorphy.com
Fri Mar 11 19:34:38 EST 2005
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.
> 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 .
That's not a permutation, that's a cycle. Permutations are sets of
disjoint cycles (which commute).
More information about the Haskell-Cafe