python itertools 产品重复到大

Question

我正在尝试制作一个 python 脚本来计算一些赢/输的机会。要做到这一点，我试图获得所有可能的输赢组合（K 是赢得比赛所需的胜利次数）：

for combination in itertools.product(['W','L'], repeat=(K*2)-1):
    if ((combination.count('L') < K) and (combination.count('W') == K)):  
        #calculate the chance of this situation happening

出于某种原因，这工作正常，直到重复变得很大（例如，如果 K=25）有人能给我一些关于如何解决这个问题的指示吗？

Answer 1

当然，当重复变大时它会失败。循环

for combination in itertools.product(['W','L'], repeat=(K*2)-1):

遍历2**(K*2-1)元素，这些元素很快就会变得非常大。例如，当 K=3 时，循环执行 32 次，但当 K=25 时，它执行 562949953421312 次。

您不应该详尽地尝试枚举所有可能的组合。一点数学知识可以帮助您：请参阅二项式分布。

以下是如何使用二项分布来解决您的问题：如果赢得单场比赛的机会是p，那么输球的机会是1-p。您想知道在n场比赛中赢k场的概率是多少。这是：

(n choose k) * p**k (1 - p)**(n - k)

这(n choose k)是恰好有k次获胜的组合数。