[Haskell-cafe] Parity of the number of inversions of a permutation
Henning Thielemann
lemming at henning-thielemann.de
Sat Mar 12 06:40:47 EST 2005
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?
More information about the Haskell-Cafe
mailing list