非递减数组合（区间）

Question

所以我的问题如下：

给定一个大小为 X 的数字和一个 A（第一个数字）、B（最后一个数字）间隔，我必须找到我可以构建的所有不同类型的非递减组合（递增或空组合）的数量.

示例：

Input: "2 9 11"

X = 2 | A = 9 | B = 11

输出：8

可能的组合 ->

[9],[9,9],[9,10],[9,11],[10,10],[10,11],[11,11],[10],[11].

现在，如果输入相同，但 X 不同，第 X = 4 行，这会发生很大变化...

[9],[9,9],[9,9,9],[9,9,9,9],[9,9,9,10],[9,9,9,11],[9,9,10,10]...

Answer 1

您的问题可以重新表述以简化为只有两个参数 X 和 N = B - A + 1 为您提供以 0 而不是 A 开头的序列。

如果您想要每个项目中正好有 X 个数字，很简单结合重复，其方程式为

x_of_n = (N + X - 1)! / ((N - 1)! * X!)

因此对于您的第一个示例，它将是

X = 2
N = 11 - 9 + 1 = 3
x_of_n = 4! / (2! * 2!) = 4*3*2 / 2*2 = 6

为此您需要添加与 X = 1 相同的内容以获得 x_of_n = 3，因此您将获得所需的总数 9.

我不知道所需输出的简单方程式，但是当您将所有方程式扩展为一个总和时，有一个很好的递归序列，您可以从 (N,X-) 计算下一个 (N,X) 1) 并对所有元素求和：

S[0] = N
S[1] = S[0] * (N + 1) / 2
S[2] = S[1] * (N + 2) / 3
...
S[X-1] = S[X-2] * (N + X - 1) / X

所以对于你给出的第二个例子，我们有

X = 4, N = 3
S[0] = 3
S[1] = 3 * 4 / 2 = 6
S[2] = 6 * 5 / 3 = 10
S[3] = 10 * 6 / 4 = 15
output = sum(S) = 3 + 6 + 10 + 15 = 34

因此您可以在此处尝试代码：

function count(x, a, b) {
  var i,
    n = b - a + 1,
    s = 1,
    total = 0;
  for (i = 0; i < x; i += 1) {
    s *= (n + i) / (i + 1); // beware rounding!
    total += s;
  }
  return total;
}

console.log(count(2, 9, 11)); // 9
console.log(count(4, 9, 11)); // 34

Update：如果你使用的语言有int类型（JS只有double），您需要使用 s = s * (n + i) / (i + 1) 而不是 *= 运算符来避免临时小数和随后的舍入问题。

更新2：功能更强大的版本，可以使用递归定义

function count(x, n) {
    return n < 1 || x < 1 ? 0 : 1 + count(n - 1, x) + count(n, x - 1);
}

其中 n = b - a + 1

非递减数组合（区间）

Non Decreasing Number Combinations (Interval)

combinations

functional-programming

numbers

intervals