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]
merge :: (Ord a) => ([a],Int) -> ([a],Int) -> ([a],Int)
merge (xs,a) (ys,b) =
case merge' (length xs) xs ys of
(zs,c) -> (zs,a+b+c)
merge' 0 [] ys = (ys,0)
merge' n xs [] = (xs,0)
merge' n (x:xs) (y:ys) =
case compare x y of
LT -> case merge' (n-1) xs (y:ys) of (zs,c) -> (x:zs,c)
GT -> case merge' n (x:xs) ys of (zs,c) -> (y:zs,c+n)
EQ -> undefined
foldb :: (a -> a -> a) -> [a] -> a
foldb f [] = undefined
foldb f [x] = x
foldb f xs = foldb f (foldb' f xs)
foldb' f (x1:x2:xs) = f x1 x2 : foldb' f xs
foldb' f xs = xs
-- Ben
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
