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.

Solution 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);
}

Solution 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").

Solution 3

void print_digit(int n,int digits)
{
   int i;
   for(i=0;i<digits;i++)
   { 
       if(n&(1<<(digits-i-1)))
       {
           putchar('1');
       }
       else
       {
           putchar('0');
       }
   }
}

print all_digits(int e)
{
   for(i=0;i<(1<<e);i++)
   {
        print_digit(i,e);
        putchar('\n');
   }
   fflush(stdout);
}

Comments

[Alfred]

why -1? the question is genuine and is 'on' topic

[Alfred]

can you please post an example, working in C without using any special built in function?

[Alfred]

if thats the case, i think 0,1,10,11 will be printed instead of 000,001,010 and 011

[thang]

no it's not. you can pre-append 0 as needed to get the right length. you asked for an algorithm, he gave you an algorithm. why don't you just implement it yourself?!

[thang]

i don't think you need (e+1). just n is ok.

[Luka Rahne]

e is like exponent. Input value is power like 3 or 4

[thang]

replace the first for loop with n=(1<<LENGTH);

[thang]

yea but if all_digits(1) is called, you output twice as many strings as needed. i guess it's ok. just not what's asked.

[Anirudh Ramanathan]

@thang Much better :) Thanks.