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