I tried to figure out how to find the even permutations out of the set {permutations [1..n]}. I have asked this question before on a different forum, and got an answer that worked namely the code was:
Import Data.List
-- number of inversions in a permutation
inversions as = sum $ map go (tails as)
where go [] = 0
go (x:xs) = length $ filter (<x) xs
evenPerm as = even (inversions as)
alternating n = [ p | p <- permutations [1..n], evenPerm p ]
I understand the last line in the code: alternating n =[p | p <- permutations [1..n], evenPerm p]. That is, the p of the set {permutations [1..n]} such that they are even permutations. The function evenPerm as I think I understand too. It is just the even elements of the set {inversion as}. The thing I truly don't understand how it is working is the inversion as function. Naively, how I would imagine things to work is take the element of the set {permutations [1..n]} [1..n] i.e. (1,2,3,..,n) and compare every other element in the set to this one and count how many moves you have to make to get it in that form, but how you go about doing that in Haskell?