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. > Example: > 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 . > tails
That's not a permutation, that's a cycle. Permutations are sets of disjoint cycles (which commute). -- wli _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
