haskell - 使用 Haskell 查找偶数排列

Question

我试图弄清楚如何从集合 {permutations [1..n]} 中找到偶数排列。我之前在另一个论坛上问过这个问题，并得到了有效的答案，即代码是:

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 ]

我理解代码中的最后一行:alternating n =[p | p <- permutations [1..n], evenPerm p] 。即p套装数量 {permutations [1..n]}这样它们甚至是排列。函数evenPerm我想我也明白。它只是集合 {inversion as} 的偶数元素。我真正不明白它是如何工作的就是作为函数的反演。天真地，我想象的工作方式是采用集合 {permutations [1..n]} [1..n] 即 (1,2,3,..,n) 的元素并比较中的所有其他元素集到这个并计算你需要进行多少次移动才能得到这种形式，但是你如何在 Haskell 中做到这一点？

Answer 1

为了获得鸟瞰图，我们想要做的是计算需要多少次交换才能对列表进行排序。 (同样，用群论的语言来说，就是将排列分解为转置。)我们使用哪种排序算法来计算交换并不影响正确性:偶数排列将生成偶数个交换，奇数排列将生成奇数个交换。无论我们如何排序，都会发生交换。

我们首先看:

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

该示例中的缩进令人困惑，但 go 是 inversions 的嵌套本地函数。它出现在 where 子句内。 go 函数统计列表中需要移动到列表中第一个元素之前的元素数量，即小于列表头部的元素。它通过过滤尾部并获取其长度来实现这一点。空列表没有头，因此有另一个模式与其匹配以保证完整性。 (否则，编译器会提示某些输入与任何模式都不匹配。)

inversions as = sum $ map go (tails as)

tails 函数来 self 们导入的 Data.List 库。它生成越来越短的最终片段列表:tails [1,2,3] = [[1,2,3] [2,3], [3]]。然后，我们将 go 映射到列表中的每个最终段，从而为我们提供每个最终段的反转计数列表。最后，我们对计数进行求和。

您经常会看到这样的函数组合:inversions = sum 。 map 去。尾部。这只是从右到左应用每个函数:tails，然后对结果进行map go，然后对其结果进行sum。 p>

例如。

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

这计算冒泡排序的交换次数。理论上我们可以执行以下交换来对列表进行排序:

[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]

这远不是交换的最小数量，但我们只需要一些排序算法的计数，而且这个很简单。

下一步是

evenPerm as = even (inversions as)

这是一个谓词，它只是告诉我们刚刚查看的计算结果是偶数还是奇数。它也可以被定义为 even 。反转，或甚至。总和。 map 去。尾部。

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

这是一个列表理解。它调用 Data.List 中的另一个函数 permutations 来生成所有排列的列表。然后，当且仅当 evenPerm p 为 true 时，它​​才会将排列 p 添加到我们的输出列表中。

这也可以写为 evenPerms = filter EvenPerm 。排列，它更短并且适用于更多类型，交替 n = EvenPerms [1..n]。也就是说，给定一个输入列表，生成其排列并对它们应用过滤器。 (这个版本的alternating仅适用于数字，因为它使用[1..n]，但该算法可以同样适用于任何带有小于运算符的东西.)

清理版本

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."

您可以尝试evenPerms "abcd" 和交替4。