python itertools product repeat to big

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 раз.

Вы не должны исчерпывающе пытаться перечислить все возможные комбинации. Немного математики могут вам помочь: см. Binomial Distribution.

Вот как использовать биномиальное распределение, чтобы решить вашу проблему: если шанс выиграть одну игру в р, то шанс потерять это 1-р. Вы хотите знать, какова вероятность выигрыша k из n игры. Это:

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

Здесь (n choose k) это число комбинаций, которые имеют точно к победы.

Answer 2

Следующая дает вам подсказку:

>>> for K in range(1,11): 
...  n = 0 
...  for combination in itertools.product(['W','L'], repeat=(K*2)-1): 
...   n+=1 
...  print (K,n), 
... 
(1, 2) (2, 8) (3, 32) (4, 128) (5, 512) (6, 2048) (7, 8192) (8, 32768) (9, 131072) (10, 524288) 
>>> 

Таким образом, вы будете иметь, чтобы ждать долго время для результата при K = 25. возможно, пришло время выработать свою вероятность, а не просто ее вычислять!