algorithm - 给定从 1 到 k 的数字，选择 d 个数字，它们的总和等于 v

Question

我正在尝试找出具有以下属性的集合中不同向量的数量:

• 一个集合是从1到k+1的k个数
• D是可以选择的元素个数
• V是元素之和

例子
k=3，d=3，v=6，结果为7；
<1, 2, 3>, <1, 3, 2>, <2, 1, 3>, <2, 2, 2>, <2, 3, 1>, <3, 1, 2>, <3 , 2, 1>

k=4，d=2，v=7，结果为2；
<3, 4>, <4, 3>
在这种情况下，<2, 5> 无效，因为 5 超过了 k 的值。

我想看看有没有数学公式可以计算出结果。如果没有公式，该算法的执行效率如何？我发现了一个相当神秘的实现，但我想知道是否可以对其进行改进。

public static int NumberOfDistinctVectors(int k, int d ,int v) {
  if((v > k * d) || (v < d)) return 0;
  if(d == 1 || v == d) return 1;
  if(v == d + 1) return d;

  int alpha = 1, beta = 0;
  if(1 < v + k - k * d) 
    alpha = v + k - k * d;

  if(k < v - d + 1)
    beta = k;
  else
    beta = v - d + 1;

  int sum = 0;
  for(int i = alpha; i <= beta; i++) {
    sum += NumberOfDistinctVectors(k, d-1, v-i);
  }

  return sum;
}

Answer 1

问题与以下内容密切相关:

What is the number of combinations to distribute b identical objects in c groups where no group contains more than n objects?

正在讨论here

试想您的数字是由对象 (+1) 组成的。所以在你的情况下

• c = d，因为每组对应你的一个数字
• b = v-d，因为您需要将至少一个 (+1) 对象放入每个 d 组
• n = k-1，因为我们假设每个组中已经有 (+1)，并且不想变得大于 k

找到下面的代码(使用 appache-commons 表示 c(N,K))

public static int NumberOfDistinctVectors(int k, int d ,int v) {

    return combinations(v-d, d, k-1);
}

//combinations to distribute b identical objects to c groups 
//where no group has more than n objects
public static int combinations(int b, int c, int n)
{
    int sum = 0;
    for(int i = 0; i <= c; i++)
    {
        if(b+c-1-i*(n+1) >= c-1)
            sum += Math.pow(-1, i) * CombinatoricsUtils.binomialCoefficient(c, i)
                   * CombinatoricsUtils.binomialCoefficient(b+c-1-i*(n+1), c-1);
    }
    return sum;
}

我也引用一下原来的回答:

"whether this is actually any more useful than the recurrence is another question"