Algorithm to generate all possible combinations of 0s & 1s, for any length of digits

Question

I would like to know how can I print n number of combinations of 1s and 0s. The number of combinations, n is user defined. The expected outputs are;

n=1;

0,1

n=2;

00,01,10,11

n=3;

000,001,010,011,100,101,110,111

etc.. etc..

The outputs will have 2^n number of combinations (where n is the number of expected digits in a single combination).

How can I do this without using any built in function? The question is language independent and is for algorithm.

Answer 1

You could just enumerate all numbers till 2^n - 1 in binary. That will leave you with the same combination.

n = 2 enumerate till 2^3 - 1 = 7 Convert to binary:

000 --> 0
001 --> 1
010 --> 2
011 --> 3
100 --> 4
101 --> 5
110 --> 6
111 --> 7

EDIT: Fixed the number of digits as well. This works

#include <stdio.h>
#define LENGTH 3
void print_binary(int n)
{
        int bit = 1<<LENGTH - 1;
        while ( bit ) {
        printf("%d", n & bit ? 1 : 0);
        bit >>= 1;
        }
        printf("\n");
}
int main(){
    int n = 1<<LENGTH, i; 
    for(i=0;i<n;i++)
        print_binary(i);
}

Answer 2

If you do not care about speed and memory, you cold use recursion which leads to a small and short solution:

public static void print01PermutationsUpToLength(final String currentString, final int upTo) {
    if (upTo == 0) {
        System.out.println(currentString);
        return;
    }
    print01PermutationsUpToLength(currentString + "0", upTo - 1);
    print01PermutationsUpToLength(currentString + "1", upTo - 1);
}

(java. Obviously, this could be done in every language which allows recursion and call-by-value or copy of String)

If you do not like the String argument, you could add a start function:

public static void print01PermutationsUpToLength(final int upTo) {
    print01PermutationsUpToLength("", upTo);
}

results:

final int upToLength = 3;
print01PermutationsUpToLength(upToLength);
000
001
010
011
100
101
110
111

Formatting can be changed like you want, this was only to see the results better.
Ordering can be changed if you switch the parts of the String construction (currentString + "0").