Show me how to flip a coin 15 times and tell me all 32,768 possible outcomes

March 22, 2012 2:27 PM

How do I find every possible outcome of an arbitrary length set of coin flips?

How can I programmatically calculate all possible outcomes of a consecutive set of binary choices, when the size of the set N is arbitrary?

Simple case, N = 3:

for my $a (0..1 ) {
  for my $b (0..1) {
    for my $c (0..1) {
        print "$a $b $c\n";
    }
  }
}

results in the output:
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

In English, you have three coin flips, therefore there are 2^3 = 8 possible scenarios for the set of 3 coin flips.

Now I want to be able to do this where the depth of those for loops is arbitrary. That is, I'd like to come up with every single possible outcome of N coin flips.

I know the answer lies somewhere with recursion, but my brain seems to be failing to make the connecting for writing the logic. My example above is in Perl, but any language or pseudo-code would be welcome in an answer.

If it's of any interest, what I'm doing is simulating all remaining possible outcomes of the NCAA bracket (16 remaining teams, N = 15 games, or 32,768 possible scenarios). Ideally, I'd construct myself a 2^N element array in which each element was an N length list of 0s and 1s.

posted by mcstayinskool to Computers & Internet (8 answers total)

Best answer: I'm no programmer, but maybe you could somehow use the fact that you're basically just counting in binary. Maybe some kind of program that converts the numbers from 0 to 2^n - 1 into binary?
posted by Proginoskes at 2:36 PM on March 22, 2012 [2 favorites]

Best answer: Every possible permutation of a string of coinflips is the same thing as every possible value of a number that many bits long. So just loop and add 1, and then print out the number binary zero padded. You don't need anything fancy like recursion or whatever. You need adding.

The loop counters you have set up are each represent a binary digit (x*2^0, x*2^1, x*2^2) and the loop ranges are implicitly adding to them.

I don't know perl but basically you want:
for int i = 0; i < max; i++ {
print_zero_padded_binary_number(i);
}

It's just counting.
posted by jeb at 2:37 PM on March 22, 2012 [1 favorite]

Response by poster: It's just counting.

Bah. Yes it is. Thank ye kindly.
posted by mcstayinskool at 2:42 PM on March 22, 2012

in perl:

$N = 15; #for example
$format = "%0$N" . "b\n"; #uuuugly
for ($i = 0; $i < 1 << $N; ++$i)
{
printf $format,$i;
}
posted by VeritableSaintOfBrevity at 2:43 PM on March 22, 2012

In bash:

read -p "How many coins? " coins
faces=(heads tails)
for ((flipset=0; flipset<1<<coins; flipset++))
do
    for ((coin=coins; --coin>=0; ))
    do
        printf "%s " ${faces[(flipset&1<<coin)>0]}
    done
    echo
done

posted by flabdablet at 4:35 PM on March 22, 2012

This is kind of ugly, but it can be done relatively succinctly in Python. For example:

import itertools
for outcome in itertools.product(*N*((0,1,),)): print outcome

will, for N=3, print

(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
posted by un petit cadeau at 4:42 PM on March 22, 2012

Python >2.6, simpler:

for i in range(N):
    print bin(i)


You can do string formatting to get the result of bin(i) how you want it.
posted by katrielalex at 6:46 PM on March 22, 2012 [1 favorite]

katrielalex, think you mean 2**N, as in for i in range(2**N).
posted by migurski at 1:12 AM on March 23, 2012