时间戳

首页 > 解决方案 > 给定从 1 到 k 的数字，选择 d 个数字，它们的总和等于 v

algorithm - 给定从 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;
}

标签： algorithmmathsum

解决方案

该问题与以下内容非常相关：

在没有组包含多个对象的组中分配b相同对象的组合数是多少？cn

这是讨论here

想想你的数字是由物体组成的（+1）。所以在你的情况下

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

找到下面的代码（使用appache-commons for 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;
}

让我也引用原始答案：

“这是否真的比复发更有用是另一个问题”

推荐阅读