Home Theory Generate All Strings of ‘n’ bits. Assume A[0….n-1] be an array of size n.

Generate All Strings of ‘n’ bits. Assume A[0….n-1] be an array of size n.

by nikoo28
28 comments 1 minutes read
void binary(int n)
{
    if(n < 1)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1] = '0';
        binary(n-1);
        A[n-1] = '1';
        binary(n-1);
    }
}

So if you supply n = 4 in the function what you get as the output is this.

0000
1000
0100
1100
0010
1010
0110
1110
0001
1001
0101
1101
0011
1011
0111
1111

You can download the code here.

You may also like

28 comments

mayank batra September 9, 2017 - 02:08

Hi Nikoo,

Could you please explain exactly where are we going back to the track …I understand this problem completely however I am new to backtracking and not able to figure out exactly at what point we are backtracking.

nikoo28 September 9, 2017 - 07:03

Hi Mayank,

Let us try to understand the code.

if(n < 1)
    printf("%s\n",arr);
else
{
    arr[n-1] = '0';
    binary(n-1);
    arr[n-1] = '1';
    binary(n-1);
}

We will follow a backwards approach since it is a recursive function.For instance lets say n = 1,

The method is called as binary(1);
arr[n-1] is set as ‘0’ (arr[1-1] = arr[0] = ‘0’)

Now we call binary(0);
since (n<1) we print arr (0 is printed)

The call returns to arr[n-1] = ‘1’
arr[1-1] is set as ‘1’ (arr[1-1] = arr[0] = ‘1’)

Now we call binary(0);
since (n<1) we print arr (1 is printed)

Thus, we got 2 outputs as possible bits 0 and 1.

Now let us suppose n = 2,

The method is called as binary(2)
arr[2-1] is set as ‘0’ (arr[2-1] = arr[1] = ‘0’)

Now we call binary(1);
From the above explanation we know that binary(1) produces an output of 0 and 1 for arr[0].
Here arr[1] is set as 0. So we get the 2 outputs (00 and 01).

The function returns to arr[n-1] = ‘1’
arr[2-1] is set as 1 (arr[2-1] = arr[1] = ‘1’)

Again we call binary(1);
This time arr[1] is set as ‘1’ and thus we get 2 more outputs (10 and 11).

We have a total of 4 outputs on screen..(00, 01, 10, 11) These are all the strings of 2 bits.

Similarly, you can work around for n = 3.
arr[2] is set as ‘0’ and binary(2) is called. This produces (000, 010, 100, 110)
arr[2] is then set as ‘1’ and binary(2) is called. This produces (001, 011, 101, 111).
These are all the strings of 3 bits.

I hope this methodology makes it clear. Please feel free to ask anything else as well.

pulkit agarwal May 12, 2017 - 01:53

my code is not working. can you help me out in my code-

#include
using namespace std;
int a[4];
void binary(int n)
{
    if(n&lt;1)
        cout<<a<<endl;
    else
    {
        a[n-1]=0;
        binary(n-1);
        a[n-1]=0;
        binary(n-1);
    }
}
int main()
{
    int num;
    cout<>num;
    binary(num);
    return 0;
}
nikoo28 May 12, 2017 - 13:56

Hi Pulkit,

Your code will not work as you have created an integer array. This is not the same as creating the character array. Please go through the code snippet I have posted once again.

pulkit agarwal May 12, 2017 - 14:06

thanks for helping me out.

pulkit agarwal May 12, 2017 - 14:58

sir.
can you explain me how this code works with an example-
void k-string(int n, int k)
{
if(n<1)
printf("%s", a); //consider array a as a global variable
else{
for(int j=0;j<k;j++)
{
a[n-1]=j;
k-string(n-1,k);
}
}
}
this code is generate all the string of length n drawn from 0…..k-1.

jayisswani February 8, 2017 - 08:27

What is the complexity of this code?
Is it O(2^n) or O(n*2^n), as we are printing the string, so it should take O(n) time?

nikoo28 March 8, 2017 - 12:44

Time Com­plex­ity — O(2^n)

trisha November 22, 2016 - 00:40

how the logic can be enhanced to handle a finite alphabet such as {A, T, G, C}.

nikoo28 November 22, 2016 - 09:14

Hi Trisha,

This should help you out

// C program to print all permutations with duplicates allowed
#include <stdio.h>
#include <string.h>
 
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
 
/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}
 
/* Driver program to test above functions */
int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n-1);
    return 0;
}
trisha November 22, 2016 - 20:14

thank u.. i have to Develop a computer program to list all the r-combinations from a set of n elements using bitstring representation.. how can that be done??

srushtee satardey July 2, 2016 - 12:29

can you please tell me how to initialize this A array?

nikoo28 November 22, 2016 - 09:12

Hi Srushtee,

Please check this link for a working version of the code.
I hope this helps you.

http://ideone.com/8xLjSQ

seecs May 31, 2016 - 13:52

Have you try to run your code?

It print out:
00
10
01
11

rather then sorted order
00
01
10
11

nikoo28 June 1, 2016 - 16:22

The problem statements never says that the output has to be in sorted order.
It just says to print all the possible combinations.

You are free to post the code that prints in sorted order though :)

Abhizeet October 28, 2015 - 09:32

Great explanation .. Please keep posting code along with such good explanation ..

Pradeek Kyahvi March 21, 2015 - 06:29

nikoo,Thanks man ,thanks for the help .

nikoo28 March 21, 2015 - 12:38

You are most welcome Pradeek.

ryan December 19, 2014 - 18:24

what exactly is the meaning of this question?

nikoo28 December 29, 2014 - 20:19

Hi Ryan,
How many strings can you form using just 1 bit? 0 and 1..right?
How many strings can you form using 2 bits? 00, 01, 10 and 11..right?
So, in this question, you need to generate all the strings of ‘n’ bits. This is it :)

Robert C November 7, 2014 - 23:58

Is it possible to make it work where you can input the length from the main function instead of only four? All my attempts have failed

nikoo28 November 8, 2014 - 02:29

Hi Robert,

Please check this link for a working version of the code.
I hope this helps you.

http://ideone.com/8xLjSQ

THILAK October 1, 2014 - 08:59

How to get the output in a sorted manner , i.e ,
000
001
010
011
100
101
110
111 ( for length 3 bits)

nikoo28 October 1, 2014 - 19:35

Hi Thilak,

The output you get is already in sorted order.
To get it in the fashion you have stated, you just need to reverse the string before printing it.

Have a look at this post-
https://studyalgorithms.com/string/print-reverse-of-a-string-using-recursion/

Thus, you can simply call this function

void reversePrint(char *str)
{
    while(*str != '\0')
    {
        reversePrint(str+1);
 
        printf("%c",str);
    }
}

when printing

if(n < 1)
{
    // printf("%s\n",A);
    reversePrint(A);

    printf("\n");  // Change the line
}

I hope this helps.

steve August 14, 2014 - 10:31

but how please explain using stack frame

nikoo28 August 16, 2014 - 23:53

Hi Steve,

Let us try to understand the code.

if(n < 1)
    printf("%s\n",arr);
else
{
    arr[n-1] = '0';
    binary(n-1);
    arr[n-1] = '1';
    binary(n-1);
}

We will follow a backwards approach since it is a recursive function.For instance lets say n = 1,

The method is called as binary(1);
arr[n-1] is set as ‘0’ (arr[1-1] = arr[0] = ‘0’)

Now we call binary(0);
since (n<1) we print arr (0 is printed)

The call returns to arr[n-1] = ‘1’
arr[1-1] is set as ‘1’ (arr[1-1] = arr[0] = ‘1’)

Now we call binary(0);
since (n<1) we print arr (1 is printed)

Thus, we got 2 outputs as possible bits 0 and 1.

Now let us suppose n = 2,

The method is called as binary(2)
arr[2-1] is set as ‘0’ (arr[2-1] = arr[1] = ‘0’)

Now we call binary(1);
From the above explanation we know that binary(1) produces an output of 0 and 1 for arr[0].
Here arr[1] is set as 0. So we get the 2 outputs (00 and 01).

The function returns to arr[n-1] = ‘1’
arr[2-1] is set as 1 (arr[2-1] = arr[1] = ‘1’)

Again we call binary(1);
This time arr[1] is set as ‘1’ and thus we get 2 more outputs (10 and 11).

We have a total of 4 outputs on screen..(00, 01, 10, 11) These are all the strings of 2 bits.

Similarly, you can work around for n = 3.
arr[2] is set as ‘0’ and binary(2) is called. This produces (000, 010, 100, 110)
arr[2] is then set as ‘1’ and binary(2) is called. This produces (001, 011, 101, 111).
These are all the strings of 3 bits.

I hope this methodology makes it clear. Please feel free to ask anything else as well.

Wally May 26, 2016 - 12:16

“We have a total of 4 outputs on screen..(00, 01, 10, 11) These are all the strings of 2 bits.”

No, this would not be the output…the output would be in this order
00, 10, 01, 11

1) Setting both the bits to 0 and base case printing 00
2) Stack unwind to set Bit 0 to 1 and call binary(n-1) again gives 10
3) Now unwind again setting Bit 1 to 1, which calls binary and sets bit 0 to 0 first and then recurse to base case…gives 01
4) unwind in #3 to give 11

“The output you get is already in sorted order.”
Neither is the output sorted

nikoo28 May 27, 2016 - 10:41

Hi Wally,

Could you please explain more regarding this.

Comments are closed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More