列表推导式：生成列表的列表

Question

你好，我正在尝试在Haskell中创建一个函数，该函数使用列表将数字分割成若干部分。例如，对于数字4，它将创建[[1,1,1,1],[1,1,2],[1,3],[2,2],[4]]。我考虑使用列表推导式来实现此功能，其中它将创建列表x，然后使用来自[1...n]（n是我想要的分区数）的数字创建更多的列表，其中所创建的列表总和为n。

到目前为止，我创建的代码如下-

partions (n:xs) = [[x|x<-[1...n], sum[x]==n]]|xs<-[1..]]

但显然它不起作用，有什么建议吗？

谢谢。

- dave

---

撤销了导致帖子被删除的编辑 - Josh Smeaton

再次提醒，@dave，你为什么要尝试删除你的两个问题？ :/ - Dan J

Answer 1

我建议尝试使用递归：为了获得n的分区，迭代数字i = 1到n，并递归生成(n-i)的分区，基本情况是1的唯一分区是1本身，0的分区是空列表。

- cadolphs

---

将partition 0更改为[[]]而不是[]，可能会使递归过程更简单。 - Joey Adams

@Joey 那是真的。我在描述我的做法时有点草率。 - cadolphs

Answer 2

这个怎么样...

import Data.List (nub, sort)

parts :: Int -> [[Int]]
parts 0 = []
parts n = nub $ map sort $ [n] : [x:xs | x <- [1..n`div`2], xs <- parts(n - x)]

试一下：

*Main Control.Monad> forM [1..5] (print . parts)
[[1]]
[[2],[1,1]]
[[3],[1,2],[1,1,1]]
[[4],[1,3],[1,1,2],[1,1,1,1],[2,2]]
[[5],[1,4],[1,1,3],[1,1,1,2],[1,1,1,1,1],[1,2,2],[2,3]]

我认为这是正确的，但效率可能不高。

- Tom Crockett

Answer 3

我对Haskell有点生疏，但也许以下代码可以指导您找到解决方案。

parts :: Int -> Int -> [[Int]]
parts 0 p = [[]]
parts x p = [(y:ys) | y <-[p..x], ys <- (parts (x - y) y)]

然后你需要使用x = n，p = 1来调用部件。

编辑

我已经修复了当x等于0时的基本情况，返回一个包含单个项的列表，该项为一个空列表。现在它可以正常工作：）

- Fede

---

也许我漏掉了什么，但是我收到一个错误：无法匹配预期类型t1->t和推断类型[[Int]]。在表达式中：parts 4 1。在“it”的定义中：it = parts 4 1。 - Matt Ellen

@Matt 我不是专家，但我认为你可能在另一个上下文中使用了 it，而 it 的类型推断与 [[Int]] 不匹配。我已经使用 WinHugs 调用了 parts 4 1，输出结果与 @dave 的示例完全相同。 - Fede

你不应该定义 'it'。在GHCi中，'it'始终是最后一次计算的结果。 - nomen

Answer 4

我发现定义一个辅助函数partitionsCap很有用，它不允许任何项大于给定值。递归使用时，它可以仅生成你想要的单调递减结果（即当你已经有[1,1,3]时，不会产生[1,3,1]）：

partitions :: Int -> [[Int]]
partitions n = partitionsCap n n

partitionsCap :: Int -> Int -> [[Int]]
partitionsCap cap n
    | n < 0  = error "partitions: negative number"
    | n == 0 = [[]]
    | n > 0  = [i : p | i <- [hi,hi-1..1], p <- partitionsCap i (n-i)]
               where hi = min cap n

---

算法的核心思想是，在将 N 分区时，从 n 逐渐减小到 1，将 i 前置到 n-i 的分区中。简化来说：

concat [map (i:) $ partitions (n-i) | i <- [n,n-1..1]]

但是错误的：

> partitions 3
[[3],[2,1],[1,2],[1,1,1]]

我们希望 [1,2] 消失。因此，我们需要限制我们要添加的分区，使它们不会超过 i：

concat [map (i:) $ partitionsCap i (n-i) | i <- [hi,hi-1..1]]
where hi = min cap n

现在，来清理一下：那个紧挨着的concat和map引起了我的注意。一点背景知识：列表推导式和列表单子是密切相关的（链接），而concatMap与列表单子中的>>=参数翻转相同。因此，我想知道：那些concat和map能否以某种方式变成>>=，并且那个>>=能否以某种方式在列表推导式中悄悄溜进去？

在这种情况下，答案是肯定的 :-)

[i : p | i <- [hi,hi-1..1], p <- partitionsCap i (n-i)]
where hi = min cap n

- Joey Adams