Combinations in coin flipping

Question

I am trying to write a little program that calculates combinations in coin flipping:

1) the user types in input how many coin tosses he wants to perform.

2) the program has to return all the possible combinations based on user input.

Example:

1 coin toss --> result: HT

2 coin tosses --> result: HH HT TH TT

3 coin tosses --> result: HHH HHT HTH HTT THH THT TTH TTT

ecc...

I have tried this approach in C++:

#include <iostream>
#include <string>
using namespace std;

// function that returns the coin face using the indexes used in for loops below
string getCoinFace(int index) {
    if(index == 0)
        return "H";
    return "T";
}

int main() {
    string result = "";

    // 3 nested loops because I toss the coin 3 times
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            for(int k = 0; k < 2; k++) {
                result += getCoinFace(i) + getCoinFace(j) + getCoinFace(k) + '\n';
            }
        }
    }

    cout << result;
    /* --OUTPUT-- 
        HHH
        HHT
        HTH
        HTT
        THH
        THT
        TTH
        TTT
    */

    return 0;
}

This works only if 3 coin tosses are performed, but I need to handle N coin tosses instead.

Maybe I need to change my approach to the problem and apply recursion but I can't figure out how.

Do you have any suggestion ?

Thanks.

Notice that if you flip n coins, you will get 2^n combinations. now if you turn H into 0 and T into 1, then you have the 2^n binary numbers from 0 to n-1. — Matthew Eleuteri
It might help to think of how an odometer in a car works -- i.e. the right-most dial increments at every time-step, and when it circles back to zero, it nudges the dial to its left forward one notch (and so on). Then think of your print-all-results problem as similar to making an odometer, except on your odometer instead of symbols 0-9 on each dial, you only need to have symbols 0-1 (aka H and T). You can create an IncrementOdometer() function that moves the odometer from its current state to the next state, and a PrintOdometer() function that prints out the current state, and call them. — Jeremy Friesner

463035818_is_not_a_number 463035818_is_not_a_number · Accepted Answer · 2019-05-10T23:05:04

It is almost trivial with std::bitset:

#include <iostream>
#include <bitset>

int main() {
    const unsigned max_n = 32;
    unsigned n = 3;
    unsigned combos = 1 << n;
    for (unsigned i=0;i<combos;++i) 
        std::cout << std::bitset<max_n>(i).to_string('H','T').substr(max_n-n,n) << "\n";               
}

In a nutshell, std::bitset transforms an unsigned you pass to the constructor to the binary representation. You can convert that to a std::string made of chars you pass to to_string. std::bitsets size is fixed at compile time, hence I used a 32bit wide bitset and then construct a substring to pick the lower bits only so that you can choose n at runtime.

Live Demo

Combinations in coin flipping

1 Answers