2

我想计算我们可以将数字划分为不同部分的方法的数量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.

先感谢您。

4

2 回答 2

2

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

假设 p = (k m - k (k-1)/2) - n。

如果 p < 0，则没有解，因为我们可以得出的最大数小于 n。假设 p >= 0。请注意，如果 p = 0，则只有一个解，因此我们假设 p > 0。

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

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

现在的问题是，有多少个最大值为 mk 和 p 的非增整数序列？这就是分区问题。即，我们可以将 p 分区多少种方式（最多分成 k 个分区）。这不是对此的封闭形式的解决方案。

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

是否有一种有效的算法用于有限数量的整数分区？

于 2020-08-23T14:44:12.233 回答
1

正如@Dave 所暗示的那样，对于简单的受限整数情况已经有了一个非常好的答案（在这里找到（与@Dave 相同的链接）：Is there an effective algorithm for integer partitioning with limited number of parts?）。

下面是一个变体，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，与链接解决方案非常相似。一个明显的区别是顶部的 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);
}

参数说明：

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

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

pStdCap这是一个更容易理解的非记忆版本。这最初是在这个答案中找到的，Is there an effective way to generate N random integers in a range that has a given sum or average?

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 的要求）。

于 2020-08-23T19:56:48.770 回答