计算具有 k 个部分的整数部分，每个部分都低于某个阈值 m

Question

我想数一数我们可以将数字 n 划分为 k 个不同的部分，其中每个部分不大于 m。

对于k := 2我有以下算法：

public int calcIntegerPartition(int n, int k, int m) {

  int cnt=0;
  for(int i=1; i <= m;i++){
    for(int j=i+1; j <= m; j++){
      if(i+j == n){
        cnt++;
        break;
      }
    }
  }
  return cnt;
}

但是我如何计算 k > 2 的整数分区？通常我有 n > 100000, k := 40, m < 10000.

提前谢谢你。

Answer 1

让我们从选择k个最大的合法数字开始：m, m-1, m-2, ..., m-(k-1)。这加起来为 k*m - k(k-1)/2。如果 m < k，则没有解决方案，因为最小分区将 <= 0。假设 m >= k。

假设 p = (km - k(k-1)/2) - n.

如果p < 0，则无解，因为我们能做的最大数小于n。假设 p >= 0。请注意，如果 p = 0，则只有一个解，因此我们假设 p > 0.

现在，假设我们从选择 k 个最大的不同合法整数开始，然后我们更正它以获得解决方案。我们的修正涉及将值向左（在数字行上）移动 1 个槽位，进入空槽位，恰好 p 次。我们有多少种方法可以做到这一点？

开始的最小值是 m-(k-1)，它最多可以向下移动 1，所以最多 m-k 次。此后，每个连续的值都可以向上移动到其前一个移动。

现在的问题是，有多少个最大值为m-k的非递增整数序列和为p？这就是分区问题。即，我们可以通过多少种方式对 p 进行分区（最多分为 k 个分区）。这不是 closed-form 解决方案。

这里已经有人对这个问题写了一个很好的答案（需要稍作修改以满足您的限制）：

Answer 2

正如@Dave 所暗示的那样，对于简单的受限整数情况已经有了一个非常好的答案（在这里找到（与@Dave 相同link）：）。

下面是 C++ 中的一个变体，它考虑了每个限制部分的最大值。首先，这是主力军：

#include <vector>
#include <algorithm>
#include <iostream>

int width;
int blockSize;
static std::vector<double> memoize;

double pStdCap(int n, int m, int myMax) {
    
    if (myMax * m < n || n < m) return 0;
    if (myMax * m == n || n <= m + 1) return 1;
    if (m < 2) return m;
    
    const int block = myMax * blockSize + (n - m) * width + m - 2;
    if (memoize[block]) return memoize[block];
    
    int niter = n / m;
    
    if (m == 2) {
        if (myMax * 2 >= n) {
            myMax = std::min(myMax, n - 1);
            return niter - (n - 1 - myMax);
        } else {
            return 0;
        }
    }
    
    double count = 0;
    
    for (; niter--; n -= m, --myMax) {
        count += (memoize[myMax * blockSize + (n - m) * width + m - 3] = pStdCap(n - 1, m - 1, myMax));
    }
    
    return count;
}

如您所见，pStdCap 与 linked 解决方案非常相似。一个明显的区别是顶部的 2 个额外检查：

if (myMax * m < n || n < m) return 0;
if (myMax * m == n || n <= m + 1) return 1;

这里是设置递归的函数：

double CountPartLenCap(int n, int m, int myMax) {
    
    if (myMax * m < n || n < m) return 0;
    if (myMax * m == n || n <= m + 1) return 1;
    if (m < 2) return m;
    
    if (m == 2) {
        if (myMax * 2 >= n) {
            myMax = std::min(myMax, n - 1);
            return n / m - (n - 1 - myMax);
        } else {
            return 0;
        }
    }
    
    width = m;
    blockSize = m * (n - m + 1);
    memoize = std::vector<double>((myMax + 1) * blockSize, 0.0);
    
    return pStdCap(n, m, myMax);
}

参数说明：

n是你要划分的整数
m是每个分区的长度
myMax 是给定分区中可以出现的最大值。（OP 将此称为阈值）

这里是现场演示https://ideone.com/c3WohV

这里是 pStdCap 的非记忆版本，更容易理解。这最初是在

的这个答案中找到的

int pNonMemoStdCap(int n, int m, int myMax) {
    
    if (myMax * m < n) return 0;
    if (myMax * m == n) return 1;
    
    if (m < 2) return m;
    if (n < m) return 0;
    if (n <= m + 1) return 1;
    
    int niter = n / m;
    int count = 0;
    
    for (; niter--; n -= m, --myMax) {
        count += pNonMemoStdCap(n - 1, m - 1, myMax);
    }
    
    return count;
}

如果你真的打算计算大到 10000 的数字的分区数，你将需要一个大的 int 库作为 CountPartLenCap(10000, 40, 300) > 3.2e37（基于 OP 的要求）。

计算具有 k 个部分的整数部分，每个部分都低于某个阈值 m

Count integer partions with k parts, each below some threshold m

algorithm

math

combinations

numbers

integer-partition