Algorithm to generate all possible arrays of ones and zeros of a given length

Question

How can I generate all possible bit combinations in an array of bits of length n. If I start with all zeros in my array then there are n possibilities to place the first bit and for these n possibilities there are n-1 possibilities to place the second bit.. unit all n bits are set to one. But so far I didn't manage to program it out.

Also many people pointed out that I can do this by counting from 0 to (2^n)-1 and printing the number in binary. This would be an easy way to solve the problem, however in this case I just let the machine counting instead of telling it where to place ones. I do this for learning, so I would like to know how to program out the ones-placing approach.

Answer 1

How would you count manually on paper? You would check the last digit. If it is 0, you set it to 1. If it is already 1, you set it back to 0 and continue with the next digit. So it's a recursive process.

The following program generates all possible combinations by mutating a sequence:

#include <iostream>

template <typename Iter>
bool next(Iter begin, Iter end)
{
    if (begin == end)      // changed all digits
    {                      // so we are back to zero
        return false;      // that was the last number
    }
    --end;
    if ((*end & 1) == 0)   // even number is treated as zero
    {
        ++*end;            // increase to one
        return true;       // still more numbers to come
    }
    else                   // odd number is treated as one
    {
        --*end;            // decrease to zero
        return next(begin, end);   // RECURSE!
    }
}

int main()
{
    char test[] = "0000";
    do
    {
        std::cout << test << std::endl;
    } while (next(test + 0, test + 4));
}

The program works with any sequence of any type. If you need all possible combinations at the same time, just put them into a collection instead of printing them out. Of course you need a different element type, because you cannot put C arrays into a vector. Let's use a vector of strings:

#include <string>
#include <vector>

int main()
{
    std::vector<std::string> combinations;
    std::string test = "0000";
    do
    {
        combinations.push_back(test);
    } while (next(test.begin(), test.end()));
    // now the vector contains all pssible combinations
}

If you don't like recursion, here is an equivalent iterative solution:

template <typename Iter>
bool next(Iter begin, Iter end)
{
    while (begin != end)       // we're not done yet
    {
        --end;
        if ((*end & 1) == 0)   // even number is treated as zero
        {
            ++*end;            // increase to one
            return true;       // still more numbers to come
        }
        else                   // odd number is treated as one
        {
            --*end;            // decrease to zero and loop
        }
    }
    return false;              // that was the last number
}