Finding even permutations using Haskell

To get a bird's eye view, we need to calculate how many swaps we will need to sort the list. (Equivalent, in the language of group theory, to decompose a permutation into transpositions.) Which sorting algorithm we use to count the swaps is irrelevant for correctness: an even permutation will generate an even number of swaps and an odd permutation of an odd number of swaps no matter how we sorting.

Let's take a look at first:

go [] = 0
go (x:xs) = length $ filter (<x) xs

      

        
        
        
      

    

The indentation in this sample is confusing but go

is a nested local function inversions

. It appears inside a sentence where

. The function go

counts the number of items in the list to wrap before the first item in the list, that is, items less than the head of the list. It does this by filtering the tail and taking up its length. An empty list has no head, so theres another sample matches it for completeness. (Otherwise, the compiler will complain that some of the inputs don't match any pattern.)

inversions as = sum $ map go (tails as)

      

        
        
        
      

    

The function tails

is from the library Data.List

we imported. It generates a list of shorter and shorter end segments: tails [1,2,3] = [[1,2,3] [2,3], [3]]

. We then map go

to each final segment in the list, giving us a list of inversion counters for each final segment. Finally, let's summarize the calculations.

You will often see things like this written as a composition of functions: inversions = sum . map go . tails

. It just applies each function from right to left:, tails

then map go

result, then sum

from result.

For example.

list == [4,3,2,1]
tails list == [[4,3,2,1], [3,2,1], [2,1], [1]]
map go (tails list) == [3,2,1,0]
sum $ map go (tails list) == 6

      

        
        
        
      

    

This counts the number of swaps to sort the bubbles. We could theoretically perform the following swaps to sort the list:

[4,3,2,1] -- 0 swaps needed to sort [1]
[4,3,1,2] -- 1 swap to sort final sequence [2,1]
[4,1,3,2] -- Which equals go [2,1]
[4,1,2,3] -- 2 additional swaps to sort [3,2,1]
[1,4,2,3] -- Which equals go [3,2,1]
[1,2,4,3]
[1,2,3,4] -- 3 additional swaps to sort [4,3,2,1]
          -- Which equals go [4,3,2,1]

      

        
        
        
      

    

This is far from the minimum number of swaps, but we just need to calculate some sorting algorithm, and it's simple.

Next step

evenPerm as = even (inversions as)

      

        
        
        
      

    

It is a predicate that simply tells us whether the result of the calculation we just looked at was even or odd. It can also be defined as even . inversions

or even . sum . map go . tails

.

alternating n = [ p | p <- permutations [1..n], evenPerm p ]

      

        
        
        
      

    

This is a list comprehension. He calls another function of Data.List

, permutations

to generate a list of all the permutations. It then adds the permutation p to our output list if and only if it evenPerm p

is true.

It could also be written as evenPerms = filter evenPerm . permutations

, which is shorter and works with more types, with alternating n = evenPerms [1..n]

. That is, given the list of inputs, generate its permutations and apply a filter to them. (This version alternating

only works with numbers because it does [1..n]

, but the algorithm can work just as well on anything with a smaller operator.)

Purified version

import Data.List

{- In the type signatures below, capitalized type names are specific types.
 - Lowercase type parameters are generic.  Ord, to the left of the => sign,
 - is the type class of all types with an ordering relation.  So, the argu-
 - ment is a list of some type a that can be ordered, and the return value
 - is a Bool, True or False.
 -}
isEvenPerm :: Ord a => [a] -> Bool
isEvenPerm = even . sum . map go . tails
  where go []     = 0
        go (x:xs) = length . filter (<x) $ xs

evenPerms :: Ord a => [a] -> [[a]]
evenPerms = filter isEvenPerm . permutations

{- This only makes sense for positive whole numbers. -}
alternating :: Integral a => a -> [[a]]
alternating n | n >= 1    = evenPerms [1..n]
              | otherwise = error "Argument must be positive."

      

        
        
        
      

    

You can try evenPerms "abcd"

and alternating 4

.