python itertools product repeat to big

Question

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

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?

Answer 1

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

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

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.

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)

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