On Fri, 11 Mar 2005, William Lee Irwin III wrote:
On Wed, Mar 09, 2005 at 12:42:09PM +0100, Henning Thielemann wrote:
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).
??? A permutation is a bijective function (here on a finite set), isn't it? Ok, the list representation is not immediately a permutation. But why a cycle?