整数分区(算法和递归)

Question

查找总和数的多少组合(代码中的变量n).例如:

3 = 1 + 1 + 1 = 2 + 1 = 3 => ANS为3

5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 => ANS是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);

}

不胜感激!

Answer 1

n通过添加一些小于或等于的数字来考虑所有结果m.正如你所说,我们称之为p(n,m).例如,p(7,3)= 8,因为有8种方法可以使7个数字小于3,如下所示:(为简单起见,我们可以假设始终按照从最大到最小的顺序添加数字)

• 3 + 3 + 1
• 3 + 2 + 2
• 3 + 2 + 1 + 1
• 3 + 1 + 1 + 1 + 1
• 2 + 2 + 2 + 1
• 2 + 2 + 1 + 1 + 1
• 2 + 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1 + 1 + 1

现在我们可以将这些组合分成两组:

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),n-m通过添加一些小于或等于的数字得到的方式的数量m.

• 如果附加m到每个组合p(n-m, m),它将导致Group1的成员.所以p(n-m, m) <= size(Group1)
• 如果您删除mGroup1的每个成员中的第一个,它将导致组合p(n-m, m).所以size(Group1) <= p(n-m, m)

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

Group1 <=== Correspon :: => 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)是n通过添加一些小于或等于m-1(小于m)的数字来得到的方法的数量.如果您重新阅读Group2的定义,您将看到这两个定义彼此相同.=> size(Group2) = p(n, m-1)

Answer 2

        / 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。

就像 OP 的递归公式一样，它将它们（如 luiges90 所说）一一相加（加上大量零的低效率）。不过幸运的是，它可以在数组内以极快的速度计算：

        / 0 (k>n)
p(k,n)={  1 (k=n)
        \ p(k+1,n)+p(k,n-k) (k<n)

Answer 3

首先，如果您想了解更多有关此函数的信息，请参阅http://mathworld.wolfram.com/PartitionFunctionP.html。

对于这个公式，请记住定义为最大成员最多为 的p(n, m)分区数。nm

因此是其最大成员最多p(n, m)为 的分区数。让我们根据最大的成员是否实际上是 来划分它们。mmm

最大成员为 的分区数m填写方式数 其中最大成员n = m + ...为 的分区数n-m最多m定义为p(n-m, m)。

根据定义，n其最大成员最多为的分区数。m-1p(n, m-1)

所以p(n, m) = p(n-m, m) + p(n, m-1)。