algorithm - 用给定的橙子和苹果制作水果篮的所有组合

Question

假设给你 A 橙子和 B 苹果。您想要创建一篮子总共有 N 个水果。你一共可以做出多少个苹果和橘子的组合？
假设 A+B >= N。

示例:
我有 6 个橙子和 6 个苹果，我想制作一个总共有 9 个水果的篮子。
所以我有 4 种不同的组合:

3 apples 6 oranges
4 apples 5 oranges
5 apples 4 oranges
6 apples 3 oranges

我想创建一个简单(高效)的算法来计算这个数字。
是否有任何数学/组合方法来计算 O(1) 中的这个数字？我找不到正确的公式。

Answer 1

这个答案将展示如何获得正确封闭公式的通用方法，而不是给出“在这里，它有效”的公式。

要获得一个封闭的公式，请使用 Stars and Bars formula和 Inclusion Exclusion ，你想找到方程解的数量:

x1 + x2 = n
s.t.
(1) 0 <= x1 <= A
(2) 0 <= x2 <= B

表示:

W(0) = #solutions to the problem regardless of restrictions
W(1) = #solutions to the problem with (1) is NOT correct (x1 > A)
W(2) = #solutions to the problem with (2) is NOT correct (x2 > B)
W(1,2) = #solutions to the problem with both (1,2) NOT correct (x1 > A and X2 > B)

根据包含排除原则，我们上面形式化的问题的答案是:

E = W(0) - (W(1) + W(2)) + W(1,2)

剩下的就是为 W(...) 提供公式，为此我们将使用星号和条号。

利用条形和星形的无约束方程和定理 2:

W(0) = Choose(N + 2 - 1, 2 - 1) = Choose(N + 1, 1) = N + 1 

为了计算 W(1) 和 W(2)，我们强制 x1/x2 为 A+1 或 B+1 ，然后照常进行，得到方程式:

x1 + x2 = N - A - 1
x1 + x2 = N - B - 1

解的数量是(再次使用定理 2):

W(1) = Choose(N - A - 1 + 2 - 1, 1) = Chose(N-A,1) = max{N-A,0}
W(2) = (similarly) = max{N-B,0}

对于 W(1,2) 我们设置两者并继续得到:

W(1,2) = Choose(N - A - 1 - B -1 + 2 - 1) = Choose(N-A-B-1,1) = max{N-A-B-1,0}

将所有这些加在一起得到最终公式:

E = W(0) - (W(1) + W(2)) + W(1,2) = 
  = N + 1 - max{N-A,0} - max{N-B,0} + max{N-A-B-1,0}

在你的例子中是:

E = 9 + 1 - 3 - 3 + 0 = 4