algorithm - 查找总和为给定数字 'p' 的 'n' 数字的排列数

Question

我正在尝试解决动态规划问题，部分问题涉及寻找一组“p”数字的排列数，总和为数字“n”。p 个数字集合中的每个数字应介于 0 到 n 之间。

例如，如果 n = 4 和 p = 3，我有以下 12 个排列

{4,0,0},{0,4,0},{0,0,4}
{2,2,0},{2,0,2},{0,2,2}
{1,3,0},{1,0,3},{0,1,3}
{1,1,2},{1,2,1},{2,1,1}

我从这种 DP 方法开始。

n(i,j) represents number of ways of representing n using i,j in p positions 

我的基本情况是

n(i,0) = n(0,i) = p   

(例如n(4,0)在p=3处为3即{4,0,0},{0,4,0},0,0,4}

递归情况

n(i,j) = n(i,j-1)*n(i-1,j)

(示例:n(1,2) = n(1,1) * n(0,2) 递归到 n(1,0) * n(0,1) * 2)

我不确定我是否在朝着正确的方向前进，因为上述方法并没有使我得到正确的答案。请指导我正确的方向。

Answer 1

与我的评论相反，如果我们同时计算集合的数量和这些集合的排列，这个问题实际上更容易解决。

如果我们只需要计数而不是实际生成每个集合，我们可以直接使用一些简单的组合数学来完成。让我们为示例固定 p = 3, n = 5 并假设我们有 n = 5 球:

o o o o o

现在的问题等同于，我们有多少种方法可以将球分成 3 组，其中每组可以有 [0, 5] 球？想象一下，如果我们有 p - 1 = 2 棍子，我们可以将它们单独放置在任何地方:在所有五个球之前、所有五个球之后以及任意两个球之间。例如:

| o o | o o o => (0, 2, 3)
o | | o o o o => (1, 0, 4)
o o o o | | o => (4, 0, 1)

请注意这些问题是如何等效的？不管怎样，我们可以放这些棍子，我们也可以将我们的 n 球分成 p 组。请注意，我们只需要 p - 1 个棍子来生成 p 个数字(第一根棍子之前的所有球都是第一组，最后一根棍子之后的所有球都是最后一组，两根棍子之间的任何球都是其他组)。

现在我们的问题是我可以用多少种方式排列我的 n 球和 p - 1 棍子？你可以把它想象成有 n + (p - 1) 槽，你只需为球选择 n 点......剩下的就是棍子去。以这种方式思考，我们可以应用组合数学的基本公式(已使用公理化的求和法则和乘积法则证明……不确定我是否见过证明):

(n + (p - 1)) Choose n = (n + (p - 1))! / n! / (p - 1)!

所以在我们的示例中，它是 7!/5!/2! = 21。您可以看到在您的示例中它将是 6!/4!/2! = 15。您错过了一些排列(例如，{0, 3, 1})。

您也可以通过简单的递归方程用 DP 解决这个问题。基本上

`f(n, p) = Sum over i = 0 to n, f(n - i, p - 1)`

并记住f的一些值。这个想法是，您为集合 S 的第一个成员选择值，然后下一个递归调用选择 S 的下一个成员，依此类推。基本情况可能类似于 f(0, p) = 1 和 f(n, 0) = 0，否则您可以使用递归情况。如果您实际上不需要集合本身，则封闭形式显然性能更高。