Generating coin flips
June 23, 2009 at 11:04 PM by Dr. Drang
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:
- It sets the all but the last flip to tails.
- It sets the last flip to tails and prints the sequence.
- It sets the last flip to heads and prints the sequence.
- It sets the second-to-last to heads and repeats Steps 2 and 3.
- It sets the third-to-last to heads, the second-to-last back to tails, and repeats Steps 2–4.
- It sets the fourth-to-last to heads, the third- and second-to-last back to tails, and repeats Steps 2–5.
- 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
