Search code examples
pythonpython-itertools

Finding all combinations of specific number of heads and tails in given number of flips

I am trying to calculate all possible combinations of given number of coin flips, using 10 as my test case for now. I believe that's Cartesian product but the last math class I had was ages ago. However, the twist is I want to calculate the most probable distributions first. This is the code I am starting with:

import itertools
for x in itertools.product(['H','T'],repeat=10):
    print(x)

This will give me all possible combinations of 10 coin flips. But the first result is all heads, which is not very likely. My thinking is to start of with an even distribution, all combinations of 5 heads and 5 tails, and then continue with 4 heads and 6 tails (plus the inverse), 3 heads and 7 tails (plus the inverse), etc. However, I'm not quite sure if I can do this with itertools or some other built-in module or combination of modules.

If I use this:

import itertools
for x in itertools.permutations(['H','H','H','H','H','T','T','T','T','T']):
    print(x)

then there are a lot of repeats, because it considers each 'H' and 'T' as unique. Any suggestions on how to tackle this?

Solution

  • From the imported multiset_permutations. This to calculate 252 permutations, (10!/5!/5!)

    >>> from sympy.utilities.iterables import multiset_permutations
>>> for item in multiset_permutations(['H','H','H','H','H','T','T','T','T','T']):
    print(item)

['H', 'H', 'H', 'H', 'H', 'T', 'T', 'T', 'T', 'T']
['H', 'H', 'H', 'H', 'T', 'H', 'T', 'T', 'T', 'T']
['H', 'H', 'H', 'H', 'T', 'T', 'H', 'T', 'T', 'T']
['H', 'H', 'H', 'H', 'T', 'T', 'T', 'H', 'T', 'T']
['H', 'H', 'H', 'H', 'T', 'T', 'T', 'T', 'H', 'T']
['H', 'H', 'H', 'H', 'T', 'T', 'T', 'T', 'T', 'H']
['H', 'H', 'H', 'T', 'H', 'H', 'T', 'T', 'T', 'T']
['H', 'H', 'H', 'T', 'H', 'T', 'H', 'T', 'T', 'T']
['H', 'H', 'H', 'T', 'H', 'T', 'T', 'H', 'T', 'T']
['H', 'H', 'H', 'T', 'H', 'T', 'T', 'T', 'H', 'T']
['H', 'H', 'H', 'T', 'H', 'T', 'T', 'T', 'T', 'H']
['H', 'H', 'H', 'T', 'T', 'H', 'H', 'T', 'T', 'T']
['H', 'H', 'H', 'T', 'T', 'H', 'T', 'H', 'T', 'T']
['H', 'H', 'H', 'T', 'T', 'H', 'T', 'T', 'H', 'T']
['H', 'H', 'H', 'T', 'T', 'H', 'T', 'T', 'T', 'H']
...
['T', 'T', 'T', 'H', 'H', 'T', 'H', 'T', 'H', 'H']
['T', 'T', 'T', 'H', 'H', 'T', 'T', 'H', 'H', 'H']
['T', 'T', 'T', 'H', 'T', 'H', 'H', 'H', 'H', 'T']
['T', 'T', 'T', 'H', 'T', 'H', 'H', 'H', 'T', 'H']
['T', 'T', 'T', 'H', 'T', 'H', 'H', 'T', 'H', 'H']
['T', 'T', 'T', 'H', 'T', 'H', 'T', 'H', 'H', 'H']
['T', 'T', 'T', 'H', 'T', 'T', 'H', 'H', 'H', 'H']
['T', 'T', 'T', 'T', 'H', 'H', 'H', 'H', 'H', 'T']
['T', 'T', 'T', 'T', 'H', 'H', 'H', 'H', 'T', 'H']
['T', 'T', 'T', 'T', 'H', 'H', 'H', 'T', 'H', 'H']
['T', 'T', 'T', 'T', 'H', 'H', 'T', 'H', 'H', 'H']
['T', 'T', 'T', 'T', 'H', 'T', 'H', 'H', 'H', 'H']
['T', 'T', 'T', 'T', 'T', 'H', 'H', 'H', 'H', 'H']

    EDIT: The OP mentioned that this may exceed the recursion limit for some cases. Here are some calculations and indeed, the number of items for a multiset_permutation can grow quite large. I guess you need to know how large your set is going to be.

    >>> from math import comb
>>> '{:,}'.format(comb(50,25))
'126,410,606,437,752'
>>> '{:,}'.format(comb(20,10))
'184,756'
>>> '{:,}'.format(comb(10,5))
'252'