Haskell的"排列"函数定义很奇怪

Question

如果我想找到列表的排列,我知道排列的数量由多项式系数给出.例如,"MISSISSIPPI"有11个字母,'S'出现4次,'I'出现4次,'P'出现两次,'M'出现一次.所以"MISSISSIPPI"的排列数等于11!/(4!4!2!)= 34650.

如果我加载GHCi并写:

ghci> import Data.List
ghci> permutations [1,2,3]

它会回来

[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]

正如所料.

但如果我写

ghci> permutations [1,0,0]

它现在会回归

[[1,0,0],[0,1,0],[0,0,1],[0,0,1],[0,1,0],[1,0,0]]

......这非常令人失望.由于有三个元素,其中两个出现两次,一个人希望只有6!/ 2!= 3个排列,即

[[1,0,0],[0,1,0],[0,0,1]]

而不是通过将列表中的每个元素视为不同而生成的六个.

1)为什么Haskell以上述方式实现"排列"(即将列表的所有元素视为不同？)

2)是否有任何标准库函数可以计算"真实"排列意义下的列表排列？

Answer 1

请记住,permutations有类型

permutations :: [a] -> [[a]]

这意味着它满足自由定理

permutations . map f = (map . map) f . permutations

适用于所有功能f.由于您可以在不影响结果列表结构的情况下任意更改参数列表的元素,因此必须确实是原始列表的索引上的函数,而不是元素.permutations

那么permutations它真正在做什么 - 它必须做什么 - 计算参数列表的索引的所有排列,然后将每个排列应用于列表并返回结果.(即,

permutations xn = (map . map) (xn!!) (permutations [0..length xn - 1])

对于有限的xn).

数学附录:

以来

xn = map (xn!!) (zipWith const [0..] xn)

对于所有人来说 xn,任何具有permutations类型的函数都必须满足

permutations xn
  = permutations (map (xn!!) (zipWith const [0..] xn)
  = (map . map) (xn!!) (permutations (zipWith const [0..] xn))

通过上面的等式xn和自由定理permutations.因此任何具有permutations类型的函数必须仅对输入列表[1]的索引起作用.

[1]从技术上讲,你可以通过使用来违反这一点seq.但仅适用于包含undefined作为元素的输入列表,在您的情况下不是这样.

Answer 2

1 - 为什么Haskell以上述方式实现"排列"(即将列表的所有元素视为不同？)

这是一个设计问题,应该深入研究.permutation将列表中的元素视为彼此不同.你可以做permutations [0, 0, 0],你还会得到一个6号列表.

2 - 是否有任何标准库函数可以在"真实"的排列意义上计算列表的排列？

是的,你有Math.Combinat.Permutations,但你可以轻松地创建自己的定义,过滤O(n * log n)使用集合的复杂性的独特组合,考虑到nub非常慢的已知:

module Main where
import Data.List (permutations)
import qualified Data.Set as Set

nubOrd :: (Ord a) => [a] -> [a]
nubOrd xs = go Set.empty xs where
  go s (x:xs)
   | x `Set.member` s = go s xs
   | otherwise        = x : go (Set.insert x s) xs
  go _ _              = []

permutations' :: (Ord a) => [a] -> [[a]]
permutations' = nubOrd . permutations

哪里permutations' [1, 0, 0]给[[1, 0, 0], [0, 1, 0], [0, 0, 1]].