Itertools для создания списка и определения вероятности

Вы можете использовать словарь для вероятностей:

 import itertools import operator probabilities = {'W':0.837, 'L':0.163} for product in itertools.product(['W','L'], repeat=3): #3=number of games p = reduce(operator.mul, [probabilities[p] for p in product]) print product, ":", p 

Функция reduce накапливает все элементы списка, используя функцию, указанную в первом аргументе, – здесь мы накапливаем их путем умножения.

Это дает вам вероятность каждой последовательности событий. Из этого вы можете легко выбрать, какой из них «Сьюзи выигрывает матч», и суммировать вероятности. Одна из возможностей сделать это:

 import itertools import operator probabilities = {'W':0.837, 'L':0.163} winProbability = 0 for product in itertools.product(['W','L'], repeat=3): #3=number of games p = reduce(operator.mul, [probabilities[p] for p in product]) if product.count('W') > 1: #works only for 3 games winProbability += p print "Susie wins:", product, "with probability:", p else: print "Susie looses:", product, "with probability:", p print "Total probability of Susie winning:", winProbability 

Условие работает только для 3 игр, но я действительно оставляю это для вас – это легко обобщить для n игр 🙂

Вам также нужно зацикливать значения n . Также обратите внимание, что «от первого до n » совпадает с «лучшим из 2n-1 ». Таким образом, мы можем сказать m = 2 * n - 1 и посмотреть, кто выигрывает большинство игр этого набора. max(set(product), key=product.count) – это короткий, но непрозрачный способ разработки, который выиграл большинство игр. Кроме того, зачем беспокоиться о представлении вероятностей со строками, а затем использовать словарь для их чтения, когда вы можете напрямую хранить значения в своих кортежах.

 import itertools pWin = 0 #the probability susie wins the match n = 0 while pWin<0.9: n += 1 m = 2 * n - 1 pWin = 0 for prod in itertools.product([0.837,0.163], repeat=m): #test who wins the match if max(set(prod), key=prod.count) == 0.837: pWin += reduce(lambda total,current: total * current, prod) print '{} probability that Susie wins the match, with {} games'.format(pWin, n) 

Я был заинтригован точкой @ wish_login, но подумал, что я попытаюсь вычислить перестановки, а не итерации через них:

 import sys if sys.hexversion >= 0x3000000: rng = range # Python 3.x else: rng = xrange # Python 2.x def P(n, k): """ Calculate permutations of (n choose k) items """ if 2*k > n: k = n - k res = 1 for i in rng(k): res = res * (ni) // (i+1) return res Ps = 0.837 # Probability of Susie winning one match Px = 0.980 # Target probability # Probability of Susie winning exactly k of n matches win_k = lambda n,k: P(n, k) * Ps**k * (1.0-Ps)**(nk) # Probability of Susie winning k or more of n matches win_k_or_more = lambda n,k: sum(win_k(n, i) for i in rng(k, n+1)) def main(): # Find lowest k such that the probability of Susie winning k or more of 2*k - 1 matches is at least Px k = 0 while True: k += 1 n = 2*k - 1 prob = win_k_or_more(n, k) print('Susie wins {} or more of {} matches: {}'.format(k, n, prob)) if prob >= Px: print('At first to {} wins, Susie has >= {} chance of winning the match.'.format(k, Px)) break if __name__=="__main__": main() 

Для Px = 0,98 это приводит к

 Susie wins 1 or more of 1 matches: 0.837 Susie wins 2 or more of 3 matches: 0.9289544940000001 Susie wins 3 or more of 5 matches: 0.9665908247127419 Susie wins 4 or more of 7 matches: 0.9837066988309756 At first to 4 wins, Susie has >= 0.98 chance of winning the match. 

Runtime – это что-то вроде O (n ^ 3) для этого алгоритма, в отличие от O (2 ^ n) для остальных.