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

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.

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

You are most welcome Pradeek.

Hi Robert,

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

http://ideone.com/8xLjSQ

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.