CODEWITHSUNDEEP
c++recursioncombinations
thwomp68
thwomp68

Reputation: 145

Combinations in coin flipping

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.

Upvotes: 1

Views: 752

Answers (1)

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122458

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

Upvotes: 1

Related Questions