Generating coin flips

In the Stochasticity post last week, I presented all the possible sequences of heads and tails for 1, 2, 3, 4, 5, and 6 coin flips. I’m way too lazy to do that by hand; I wrote a short program to generate the sequences and then forgot to include it in the post. Here it is:

 1:  #!/usr/bin/python
2:  from __future__ import division
3:
4:  f = 6
5:  flips = list('-' * f)
6:
7:  def sequence(m):
8:    global flips
9:    if m == 1:
10:      flips[-m] = 'T'
11:      print ''.join(flips)
12:      flips[-m] = 'H'
13:      print ''.join(flips)
14:    else:
15:      flips[-m] = 'T'
16:      sequence(m-1)
17:      flips[-m] = 'H'
18:      sequence(m-1)
19:
20:  sequence(len(flips))


As presented above, it generates the 64 possible sequences of 6 coin flips—TTTTTT, TTTTTH, TTTTHT, and so on. Changing the value of f in Line 4 changes the number of flips.

The heart of the program is the sequence function in Lines 7–18. Basically, sequence does what you would do if you wanted to systematically write out every possible sequence of flips:

1. It sets the all but the last flip to tails.
2. It sets the last flip to tails and prints the sequence.
3. It sets the last flip to heads and prints the sequence.
4. It sets the second-to-last to heads and repeats Steps 2 and 3.
5. It sets the third-to-last to heads, the second-to-last back to tails, and repeats Steps 2–4.
6. It sets the fourth-to-last to heads, the third- and second-to-last back to tails, and repeats Steps 2–5.
7. It sets the fifth-to-last…

This is a recursive procedure, very much like the Towers of Hanoi problem, which is why sequence is written as a recursive function.

The program prints out one sequences per line. To get the multicolumn format in the post,

TTTTTT   TTHTTT   THTTTT   THHTTT   HTTTTT   HTHTTT   HHTTTT   HHHTTT
TTTTTH   TTHTTH   THTTTH   THHTTH   HTTTTH   HTHTTH   HHTTTH   HHHTTH
TTTTHT   TTHTHT   THTTHT   THHTHT   HTTTHT   HTHTHT   HHTTHT   HHHTHT
TTTTHH   TTHTHH   THTTHH   THHTHH   HTTTHH   HTHTHH   HHTTHH   HHHTHH
TTTHTT   TTHHTT   THTHTT   THHHTT   HTTHTT   HTHHTT   HHTHTT   HHHHTT
TTTHTH   TTHHTH   THTHTH   THHHTH   HTTHTH   HTHHTH   HHTHTH   HHHHTH
TTTHHT   TTHHHT   THTHHT   THHHHT   HTTHHT   HTHHHT   HHTHHT   HHHHHT
TTTHHH   TTHHHH   THTHHH   THHHHH   HTTHHH   HTHHHH   HHTHHH   HHHHHH


I used TextMate’s column selection tool and did some simple cutting and pasting.

Because the Stochasticity post was mostly concerned with runs of tails, I wrote the program to start with all tails and gradually shift to heads. By switching Lines 10 and 12 and Lines 15 and 17, you could generate a sequence that starts with all heads and gradually shifts to tails.

HHHHHH   HHTHHH   HTHHHH   HTTHHH   THHHHH   THTHHH   TTHHHH   TTTHHH
HHHHHT   HHTHHT   HTHHHT   HTTHHT   THHHHT   THTHHT   TTHHHT   TTTHHT
HHHHTH   HHTHTH   HTHHTH   HTTHTH   THHHTH   THTHTH   TTHHTH   TTTHTH
HHHHTT   HHTHTT   HTHHTT   HTTHTT   THHHTT   THTHTT   TTHHTT   TTTHTT
HHHTHH   HHTTHH   HTHTHH   HTTTHH   THHTHH   THTTHH   TTHTHH   TTTTHH
HHHTHT   HHTTHT   HTHTHT   HTTTHT   THHTHT   THTTHT   TTHTHT   TTTTHT
HHHTTH   HHTTTH   HTHTTH   HTTTTH   THHTTH   THTTTH   TTHTTH   TTTTTH
HHHTTT   HHTTTT   HTHTTT   HTTTTT   THHTTT   THTTTT   TTHTTT   TTTTTT