[Haskell-cafe] Parity of the number of inversions of a permutation
Henning Thielemann
lemming at henning-thielemann.de
Tue Mar 15 09:31:32 EST 2005
On Tue, 15 Mar 2005, Ben Rudiak-Gould wrote:
> Henning Thielemann wrote:
>> 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.
>
> This is a rather nice little problem. I think this works:
>
>
> countInversions :: (Ord a) => [a] -> Int
>
> countInversions [] = 0
> countInversions xs = snd $ foldb merge [([x],0) | x <- xs]
Yes, zipping together one-node lists is a nice idea to prevent dividing as
in the classic divide&conquere scheme.
More information about the Haskell-Cafe
mailing list