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.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
