CODEWITHSUNDEEP
algorithm
Alfred
Alfred

Reputation: 21406

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

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.

Upvotes: 6

Views: 16543

Answers (4)

Andy
Andy

Reputation: 89

This is my view to this problem.Given an array of characters and you want to find the k combination of that using the entire array. To address this question our Array contains : ['0','1'].

Let's say we have a char set[] = new {'0','1'};

Below method will give you any number of combination of zero and one. I have testing it with combination of 0 and 1 with dataset of 50 characters.

public  void printLengthRec(char[] inputSet, String prefix, int k) {
    int sizeOfInputArray=inputSet.length;
    //TerminationCase: k is 0, print prefix
    if (k == 0) {
        System.out.println(prefix);
        return;
    }    
    // One by one add all characters from set and recursively 
    // call for k equals to k-1
    for (int i = 0; i < 2; ++i) {
        // Next character of input added
        String newPrefix = prefix + set[i]; 
        printLengthRec(inputSet, newPrefix, k - 1); 
    }
}

Upvotes: 0

tb-
tb-

Reputation: 1290

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

Upvotes: 3

Luka Rahne
Luka Rahne

Reputation: 10457

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

Upvotes: 2

Anirudh Ramanathan
Anirudh Ramanathan

Reputation: 46738

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

Upvotes: 13

Related Questions