Haskell，重复+排列的组合

Question

假设我有一个包含元素的列表，例如[1,2,3,4,5,6,7,8]。我想创建长度为 N 的该元素的所有排列。

因此，对于N = 4，它将是[[1,1,1,1],[1,1,1,2],[1,1,2,1],[1,2,1,1],[2,1,1 ,1],..] 等等。

comb :: Int -> [a] -> [[a]]
comb 0 _ = [[]]
comb _ [] = []
comb m (x:xs) = map (x:) (comb (m-1) xs) ++ comb m xs

现在，为了首先获得这个列表，我找到了列表中所有重复的组合，所以 [[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,1,4],[1,1, 1,5],...] 对于每个列表，我都会找到所有排列，如果排列不在列表中，我会将其添加到列表中。

permutations1 :: Eq a => [a] -> [[a]]
permutations1 []   = [[]]
permutations1 list = [(x:xs) | x <- list, xs <- permutations1 $ delete1 x list]

delete1:: Eq a => a -> [a] -> [a]
delete1 _ [] = [] 
delete1 a (b:bc) | a == b = bc 
                 | otherwise = b : delete1 a bc

这就是我得到想要的答案的方式。

我知道这真的(真的)很糟糕，但我对 haskell 的理解还不足以编写结合这些函数的函数。

Answer 1

这称为放回抽样。在 haskell 中你可以使用 replicateM和列表的单子(monad)行为(即非确定性计算)

\> import Control.Monad (replicateM)
\> length $ replicateM 4 [1..5]   -- should output 5^4
625
\> replicateM 4 [1..5]
[[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,1,4],[1,1,1,5],[1,1,2,1],[1,1,2,2],[1,1,2,3],[1,1,2,4],[1,1,2,5]] ....

如果您想从规模为 5 的总体中获得规模为 4 的样本并进行替换，那么对于 4 个项目中的每一个，您都有 5 个选择；因此，您复制每个[1..5] 4次，因此replicateM 4。

Monad type class (即 M 部分)表示您应该能够将这些中间值绑定(bind)在一起。

The list instance of monad type class模型非决定论。也就是说，它表示每个项目都是不确定的，但它可以是 [1..5] 值之一，并且将它们绑定(bind)在一起需要一个外部产品 所有非确定性值；因为如果您有 4 个项目，每个项目有 5 个可能的值，那么您就有 5^4 可能的最终输出。