algorithm - 找到与数据一致的分数的所有可能组合

Question

所以我一直在利用业余时间解决一个问题，但我陷入了困境。这就是我现在所在的地方。我有一个号码40。它代表球员。我得到了其他数字 39, 38, .... 10。这些代表前 30 名玩家的分数 (1 -30)。其余球员(31-40)的得分未知。我想做的是找出有多少个分数组合与给定的数据一致。

举一个更简单的例子:如果你有 3 名玩家。一方的得分为 1。则得分的可能组合数为 3 (0,2; 2,0; 1,1)，其中 (a,b) 代表玩家一和玩家二的获胜次数， 分别。 (3,0) 的组合不起作用，因为没有人可以获得 3 场胜利。 (0,0) 也不起作用，因为我们总共需要 3 场胜利(并且用 0,0 无法获得胜利)。

我已经找到了可能的游戏总数。这是所玩比赛的总数，这意味着它是获胜的总数。 (没有平局。)最后，我有一个变量表示每个玩家的最大获胜次数(比玩家总数少一。没有玩家可以拥有比这更多的胜利。)

我尝试通过将 N 个胜利分配给每个玩家，然后减去不符合标准的组合来找到独特组合的数量。例如，要找出多种方法让 5 个人获得 10 场胜利，并且每人获得不超过 4 场胜利，您可以使用: C(14,4) - C(5,1)*C(9,4) + C(5,2)*C(4,4) = 381。C(14,4) 来自公式 C(n +k-1，k-1)(我相信谷歌酒吧和 strip )。接下来是去掉带有 5 的(不允许)，但添加我们减去两次的那些。

是的，必须有一种更简单的方法。最后，数字变得如此之大，以至于我不确定我的计算机是否能够充分处理它们。我们谈论的是 C(780, 39)，即 1.15495183 × 10^66。无论如何，应该有更好的方法来做到这一点。

回顾一下，您有 40 个人。前30人的分数是10-39。后10人的分数未知。您能产生多少分数，才符合标准:所有分数加起来就是可能获胜的总分，并且每个玩家最多只能获得 39 场胜利。

想法？

Answer 1

生成函数:

由于问题更多地与数学有关，但仍在编程 QA 网站上，因此让我为您提供一个部分解决方案，该解决方案可以使用符号代数(例如 Mathematica 的 Maple)来解决许多此类问题。我强烈建议您阅读一本介绍组合学的书，这些问题在那里都有答案。

首先，前 30 名得分 10-39 的玩家(总分 735)有点转移注意力 - 我们想要做的是解决其他问题，其余 10 名得分可能在 (0...39) 范围内的玩家。

如果我们将玩家可能的分数视为多项式:

f(x) = x^0 + x^1 + x^2 + ... x^39

例如，x^2 的值是 2，请考虑一下它的样子

f(x)^10    

这代表所有 10 名玩家的总得分，即。 x^385 的系数是 2002，这表示 10 名玩家有 2002 种方法可以得到 385 分。 Wolfram Alpha(IMO 的一种编程语言) can evaluate this for us .

如果您想知道有多少种可能的方法，只需将表达式中的 x=1 替换为 8,140,​​406,085,191,601，恰好是 39^10(毫不奇怪!)

为什么这有用？

虽然我知道对于某些人来说，为一个可以在纸上解决的简单问题设置所有这些机制可能看起来很愚蠢 - generating functions 的方法当问题变得困惑时很有用(并且可以进行渐近分析)。考虑同样的问题，但现在我们限制玩家只能得分素数(2,3,5,7,11，...)。他们中的 10 个人可以通过多少种方式获得特定的数字，比如 344？只需修改您的 f(x):

f(x) = x^2 + x^3 + x^5 + x^7 + x^11 ...

然后重复这个过程! ( I get [x^344]f(x)^10 = 1390)。