查找ocaml中给定数量的足球比赛的所有排列

Question

我必须编写函数系列：int - > int - >结果列表列表，所以第一个int表示游戏数量，第二个int表示获得的点数。

我已经通过创建所有排列并过滤列表来考虑经验解决方案，但我认为这将是非常脏的解决方案，包含许多代码行。我找不到另一种方法来解决这个问题。

给出以下类型

type result = Win (* 3 points *)
| Draw (* 1 point *)
| Loss (* 0 points *)

所以，如果我打电话

series 3 4

解决方案应该是：

[[Win ;Draw ;Loss]; [Win ;Loss ;Draw]; [Draw ;Win ;Loss];
[Draw ;Loss ;Win]; [Loss ;Win ;Draw]; [Loss ;Draw ;Win]]

也许有人可以给我一个提示或代码示例如何开始。

Answer 1

考虑调用series n (n / 2)形式，并考虑所有游戏都是Draw或Loss的情况。在这些限制下，答案的数量与2^n/sqrt(n)成正比。 （伙计们在网上从斯特林的近似中得到这个。）

这不包括任何人赢得比赛的系列赛。因此，实际结果列表通常会比这更长。

我的结论是，可能的答案数量巨大，因此您的实际案例将会很小。

如果您的实际案例很小，使用蛮力方法可能没有问题。

与您的说法相反，蛮力代码通常很短且易于理解。

您可以轻松编写一个函数来列出从n获取的所有可能的Win, Lose, Draw长度序列。然后，您可以过滤它们以获得正确的总和。渐渐地，由于上面描述的近指数行为，这可能仅比最快的算法差一点。

Answer 2

一个简单的递归解决方案就是这样：

• 如果有0场比赛和0点获胜，则只有一个（空）解决方案
• 如果有0场比赛可以玩，1个或更多点可以获得，那么就没有解决方案。
• 否则，p积分必须在g游戏中获得：p游戏中g-1点的任何解决方案都可以扩展到解决方案，在它前面添加一个Loss。如果p>=1，你可以类似地在Draw游戏中为p-1的任何解决方案添加g-1，如果p>=3，可能还有可能从Win开始。