python itertools产品重复大 [英] python itertools product repeat to big

问题描述

我正在尝试制作一个python脚本来计算一些赢/输的机会. 为此，我正在尝试将所有可能的组合排除在输赢之外(K是赢得比赛所需的获胜次数):

I'm trying to make a python script to calculate some win/loss chances. to do this i'm trying to get all possible combinations off wins and losses (K is the number of wins needed to win the game):

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) 有人可以给我一些如何解决这个问题的指示吗?

for some reason this works fine, until the repeat becomes to big (for instance if K=25) Can someone give me some pointers on how to solve this?

推荐答案

当然，当重复次数很大时，它会失败.循环

Of course it fails when the repeat becomes large. The loop

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

通过2**(K*2-1)元素迭代，该元素很快变得非常大.例如，当K = 3时，循环执行32次，但是当K = 25时，循环执行562949953421312次.

iterates through 2**(K*2-1) elements, which becomes prohibitively large very quickly. For example, when K=3, the loop executes 32 times, but when K=25 it executes 562949953421312 times.

您不应穷举所有可能的组合.一点数学可以帮助您:请参阅二项分布.

You should not exhaustively try to enumerate all possible combination. A little bit of mathematics can help you: see Binomial Distribution.

以下是使用二项分布解决问题的方法:如果赢得一场比赛的机会是 p ，那么输掉机会的机会是 1-p .您想知道从 n 个游戏中赢得 k 的概率是多少.它是:

Here is how to use the Binomial Distribution to solve your problem: If chance to win a single game is p, then the chance to lose is 1-p. You want to know what is the probability of winning k out of n games. It is:

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

这里(n choose k)是完全 k 个获胜的组合的数量.

Here (n choose k) is the number of combinations that have exactly k wins.

这篇关于python itertools产品重复大的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！