March 22, 2012 2:27 PM Subscribe

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:

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) 1 user marked this as a favorite

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.

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]

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]

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

$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:

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

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

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:

You can do string formatting to get the result of

posted by katrielalex at 6:46 PM on March 22, 2012 [1 favorite]

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

posted by migurski at 1:12 AM on March 23, 2012

This thread is closed to new comments.

posted by Proginoskes at 2:36 PM on March 22, 2012 [2 favorites]