logo标签列表

整数划分（算法和递归）

algorithmrecursioninteger-partition
27
找出一个和数的组合总数（变量n在代码中）。例如：

3 = 1+1+1 = 2+1 = 3 => 答案为3

5 = 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1 => 答案为7

在以下示例中，m是最大数字，n是总和，目标是找出它有多少个(sum)组合。

我只想知道为什么 p(n, m) = p(n, m - 1) + p(n - m, m) ？

这里是代码:

int p (int n, int m)
{
    if (n == m)
        return 1 + p(n, m - 1);
    if (m == 0 || n < 0)
        return 0;
    if (n == 0 || m == 1)
        return 1;

    return p(n, m - 1) + p(n - m, m);

}

感谢您！

1
所以你想一个一个地计算每个排列？ - luiges90
1
我认为这是组合，对于这种情况，3+2和2+3没有区别。 - PlusA
我猜它来自这里：http://en.wikipedia.org/wiki/Partition_(number_theory)#Intermediate_function - nhahtdh
1
这里的函数使用不大于m的数字（小于或等于），但是维基上的情况是使用大于或等于k的数字。 - PlusA
我猜您希望我们通过组合论的方法来证明p(n,m)的递归关系，但是您忘记给出该函数的组合定义！这不是一个公平的要求。 - Colonel Panic
4个回答
27
考虑通过加一些小于或等于m的数字来得到所有结果为n的方式。正如你所说，我们将其称为p(n,m)。例如， p(7,3)=8，因为有以下8种方法可以用小于3的数字使7变成：（为简单起见，我们可以假设总是按从大到小的顺序添加数字）
现在我们可以将这些组合分为两组：
1. 第一个元素等于m的组合（在我们的例子中为=3）： - 3+3+1 - 3+2+2 - 3+2+1+1 - 3+1+1+1+1
2. 第一个元素小于m的组合： - 2+2+2+1 - 2+2+1+1+1 - 2+1+1+1+1+1 - 1+1+1+1+1+1+1
由于p(n,m)的每个成员都可以属于Group1或Group2，我们可以说p(n,m)=size(Group1)+size(Group2)。现在，如果我们证明size(Group1)=p(n-m,m)和size(Group2)=p(n,m-1)，通过代入我们可以得到p(n,m)=p(n-m,m)+p(n,m-1)。

证明size(Group1)=p(n-m, m):

根据以上定义，p(n-m, m)是通过添加一些小于或等于m的数得到n-m的方式数。

  • 如果将m附加到p(n-m, m)的每个组合中，结果将是Group1的成员。因此，p(n-m, m) <= size(Group1)
  • 如果从Group1的每个成员的第一个m中删除，结果将得到p(n-m, m)的组合。因此，size(Group1) <= p(n-m, m)

=> size(Group1) = p(n-m, m)。在我们的例子中：

Group1 <===对应===> p(4, 3) ：

  • 7=3+3+1 <===========> 3+1=4
  • 7=3+2+2 <===========> 2+2=4
  • 7=3+2+1+1 <=======> 2+1+1=4
  • 7=3+1+1+1+1 <===> 1+1+1+1=4

因此，p(n-m,m)的任何成员都与Group1存在一一对应关系，它们的大小相等。

证明size(Group2)=p(n, m-1):

根据定义，p(n,m-1)是通过添加一些小于或等于m-1（小于m）的数字来得到n的方式数。如果您重新阅读Group2的定义，您会发现这两个定义彼此相同。=> size(Group2) = p(n, m-1)

有人能告诉我在考虑返回值0和1的情况下，如何生成以下值的吗？ 3+3+1 3+2+2 3+2+1+1 3+1+1+1+1 这是在执行p(4,3)时产生的。 - Monte San
7
        / 0 (k>n)
p(k,n)={  1 (k=n)
        \ p(k+1,n)+p(k,n-k) (k<n)

n的划分数为p(1,n)。

p(k,n)是n的划分数，只允许添加大于等于k的加数。

与原帖中的递归公式类似，它们（如luiges90所说）一个接一个地添加（存在大量的零元素使其效率低下）。不过，幸运的是，它可以在数组内快速计算：

#include <stdio.h>

/* 406 is the largest n for which p(n) fits in 64 bits */
#define MAX 406
long long int pArray[MAX][MAX];

/* Emulate array starting at 1: */
#define p(k,n) pArray[k-1][n-1]

int main(int argc, char **argv) {
    int n, k;
    for (n = 1; n < MAX; n++) {
        for (k = n; k > 0; k--) {
            if (k > n) {
                p(k, n) = 0;
            } else if (k == n) {
                p(k, n) = 1;
            } else {
                p(k, n) = p(k, n - k) + p(k + 1, n);
            }
        }
    }
    for (n = 1; n < MAX; n++) {
        printf("p(%d)=%lld\n", n, p(1, n));
    }
}
5

如果您想了解更多关于此函数的内容，请参考http://mathworld.wolfram.com/PartitionFunctionP.html

对于这个公式，需要注意的是 p(n, m) 被定义为最大元素不超过 m 的数字 n 的拆分数量。

因此，p(n, m) 是最大元素不超过 m 的数字 n 的拆分数量。让我们根据最大元素是否为 m 来进行分类。

最大元素为 m 的拆分数量是填充 n=m+... 的方式数目，即最大元素不超过 m 的数字 n-m 的拆分数量，根据定义可知为 p(n-m, m)。

最大元素不超过 m-1 的数字 n 的拆分数量，根据定义为 p(n, m-1)。

因此，p(n, m) = p(n-m, m) + p(n, m-1)。

2

将p(n, m)定义为所有组合中，和为n且每个加数都小于或等于m的数量。关键点在于证明以下递归方程：

p(n, m) - p(n, m - 1) = p(n-m, m)          (1)

(1)式子左边是p(n, m)和p(n, m-1)的差值，它们是包含至少一个加数为m的所有组合的数量，剩余的和为n-m(总和为n)，并且每个加数都小于或等于m。但这恰好意味着p(n-m, m)，这是(1)式子右边的内容。

显然，问题的答案应该是p(n, n)。

我只是不理解为什么剩余部分是p(n-m, m)，能否用其他方式解释一下？如果您能用中文更详细地解释就更好了！ - PlusA
@PlusA 我不确定用中文回答是否好。我们这样想：在P(n, m)中但不在p(n, m-1)中的所有组合的特点是什么？首先，这些组合必须有一个固定成员，即 m（否则它也属于p(n, m-1)）。其次，其余成员的总和必须为 n-m（使得总和为 n）。此外，其余成员最多可以为 m。因此，这些组合的数量应该是 p(n-m, m)。清楚吗？ - Hui Zheng
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接