Haskell 获取总和为 X 的所有数字

Question

我需要在 haskell 中创建一个函数，它接收一个数字并返回一个列表列表，其中列表包含所有数字的组合，其总和是收到的数字。

很难解释，所以这是一个例子：

sum1 4 = [ [4], [3,1], [2,2], [1,3], [1,1,2], [1,2,1] , [2,1,1] ]

sum1 3 = [ [3], [2,1], [1,2], [1,1,1]

我需要用递归和理解列表来做到这一点

编辑

这是我的代码：

sum1 n = sum3 (sum2 1 (n-1) n)
sum2 x y n = if ((x+y)==n && x>0 && y>0) then [x,y]:sum2 (x+1) (y-1) n else []
sum3 [] = []
sum3 (x:xs) = sum4 x 1 : sum3 xs
sum4 [] t = []
sum4 (x:xs) t = if not (x == t) then (sum1 x) else x

是的，这是一次过分的考试，但我不知道该怎么做

Answer 1

我会假设这是家庭作业（IMO 更难），所以我现在不会破坏一切。

如果您仔细考虑一下，您应该会看到基本上有两种操作可以从xs总和n为 的列表到总和为 的列表n+1：

• 你可以添加另一个 1
• 你可以添加1一些x在xs

因此，如果您设法实现这两种操作，您的任务就会容易得多。

第一个并不难（提示 (1:)是一个附加1到某个列表的函数- 现在你必须映射这个......）

第二个有点难，尽管几乎相同的分而治之的想法会帮助你。

这是我将如何开始：

add1Somewhere :: Num a => [a] -> [[a]]
add1Somewhere [i] = [[i+1]]
add1Somewhere (i:is) = ???

（是的，这是一个偏函数）

评论：

• 正如您在下面看到的，您实际上不必在1某处插入额外的内容或选择任何x输入xs- 使用第一个x输入xs并添加到第一个位置就足够了
• 我暗示的算法有时会产生相同的结果 - 例如，如果你有一个，[1,1]那么你可以在[2,2]稍后以两种方式结束：[1,1] -> [2,1] -> [2,2]并且[1,1] -> [1,2] -> [2,2]-Data.List.nub如果你改变你的算法以产生有序/过滤的结果，这些可以被删除（不生产[1,1] -> [1,2]）
• 你的例子遗漏了一些东西[1,1,1,1]，老实说，我不知道这个练习是否暗示了一个这样的顺序
• 你可能应该看看concatMap（或concat）
• 这与@cirdec 暗示的算法不同（可能他的速度更快）-但是如果您在某个地方插入一个额外的 1，同样的重复问题也适用

解决方案

因为已经有一段时间了，你说这是一个旧的考试问题，我认为可以破坏它（如果你不想，请不要继续阅读）

所以这是一个可能的解决方案（不关心任何性能问题）：

import Data.List (nub)

sum1 :: (Eq a, Num a) => a -> [[a]]
sum1 1 = [[1]]
sum1 n = nub $ concatMap add1Somewhere ns ++ map (1:) ns
  where ns = sum1 (n-1)

add1Somewhere :: Num a => [a] -> [[a]]
add1Somewhere [i] = [[i+1]]
add1Somewhere (i:is) = ((i+1):is) : map (i:) (add1Somewhere is)

请注意，此用途concatMap以及nub两者都可能适用，也可能不适用于此。

我希望你明白基本的想法

显然更好的解决方案

哎呀 - 我只是注意到你可以摆脱所有有问题的函数，比如concat，nub无论如何，因为只需1在第一个列表元素前面加上或递增就足够了- 无论如何，递归将提供所有需要的排列（我提到的不同路径正是排列）-尽管顺序有所不同：

sum1 :: (Eq a, Num a) => a -> [[a]]
sum1 1 = [[1]]
sum1 n = map add1 ns ++ map prep1 ns
  where ns          = sum1 (n-1)
        prep1 is    = 1:is
        add1 (i:is) = (i+1):is

当然，map如果你愿意，你可以用列表理解替换

证明这可以找到所有排列

by Induction on n（假设仅正自然数）

请n=1注意这[1]是唯一可能的列表

现在假设我们找到了所有排列n>0并查看了一些xs 总结为n+1的列表（显然列表需要非空）

现在，第一个元素x的xs = x:ys将是两种1或>1

• x=1- 在这种情况下prep1将提供xs因为ys我们的算法通过归纳发现（注意sum ys = sum xs - 1 = n）
• x>1- 在这种情况下(x-1):ys，我们的算法通过归纳发现add1并将创建xs（再次因为sum ((x-1):ys) = sum xs - 1 = n）