Generate Binary Sequence

Question

I want to generate permutations of string of 5 0s followed by the permutations of 4 0s and a single 1, followed by the permutations of 3 0s with 2 1s etc? My code is as follows:

#include<stdio.h>
int main(){

int i,j,k,l,s[5];
for(i=0;i<5;i++)
  s[i]=0;
for(k=0;k<5;k++)
       printf("%d  ",s[k]);
   printf("\n");
printf("---------------------------------------------\n");

for(i=0;i<5;i++){
  for(j=0;j<5;j++)
    if(i==j)
      s[j]=1;

    else
      s[j]=0;
    for(k=0;k<5;k++)
       printf("%d  ",s[k]);
   printf("\n");
                 }
printf("---------------------------------------------\n");

for(i=0;i<5;i++){
  for(k=0;k<5;k++)
    s[k]=0;
  s[i]=1;
  for(j=i+1;j<5;j++){
    s[j]=1;
    for(k=0;k<5;k++)
       printf("%d  ",s[k]);
    printf("\n");
    for(k=j;k<5;k++)
       s[k]=0;
                    }

                 }

printf("---------------------------------------------\n");
for(i=0;i<5;i++){

  for(j=i+1;j<5;j++){
    for(k=0;k<5;k++)
       s[k]=0;
    s[i]=1;
    s[j]=1;
    for(l=j+1;l<5;l++){
        s[l]=1;
    for(k=0;k<5;k++)
       printf("%d  ",s[k]);
    printf("\n");
    for(k=l;k<5;k++)
       s[k]=0;
                      }
                    }

                 }


}

So output is

0  0  0  0  0  
---------------------------------------------
1  0  0  0  0  
0  1  0  0  0  
0  0  1  0  0  
0  0  0  1  0  
0  0  0  0  1  
---------------------------------------------
1  1  0  0  0  
1  0  1  0  0  
1  0  0  1  0  
1  0  0  0  1  
0  1  1  0  0  
0  1  0  1  0  
0  1  0  0  1  
0  0  1  1  0  
0  0  1  0  1  
0  0  0  1  1  
---------------------------------------------
1  1  1  0  0  
1  1  0  1  0  
1  1  0  0  1  
1  0  1  1  0  
1  0  1  0  1  
1  0  0  1  1  
0  1  1  1  0  
0  1  1  0  1  
0  1  0  1  1  
0  0  1  1  1

Output is ok. However in my code I use different for loops for different cases. Is it possible to use better approach so that length of the code is reduced?

Answer 1

One approach follows. This solution needs O(n) space and each output string requires O(n) time.

#include <stdio.h>
#include <stdlib.h>

char *buf;

// Print combinations of m 1's in a field of n 0/1's starting at s.
void print_combinations(char *s, int n, int m)
{
  // If there is nothing left to append, we are done.  Print the buffer.
  if (m == 0 && n == 0) {
    *s = '\0';
    printf("%s\n", buf);
    return;
  }
  // Cut if there are more 1's than positions left or negative numbers.
  if (m > n || m < 0 || n < 0) return;
  // Append a 0 and recur to print the rest.
  *s = '0';
  print_combinations(s + 1, n - 1, m);
  // Now do the same with 1.
  *s = '1';
  print_combinations(s + 1, n - 1, m - 1);
}

int main(void)
{  
  int n = 5;
  buf = malloc(n + 1);
  for (int m = 0; m <= n; m++) {
    print_combinations(buf, n, m);
    printf("-----\n");
  }
  return 0;
}

Answer 2

You could use a recursive function like so - you don't have to print the result when finished, you could add it to a list etc.

The function works by starting with an empty string. At each step you add one more character - in this case you add either a 0 or a 1.

If a 1 is added we account for this by decrementing the ones value on the next call to the function. (In a more general case you could pass a list of all the elements to be permuted - then the process would be to pick from this list, add it to your permutation and remove it from the list. You repeat that until the list is empty and you have permuted all of the elements in the list.)

When the string reaches the desired length we have finished and so we return.

#include <stdio.h>

void recurse(char *str, int length, int maxLength, int ones)
{
    if (length == maxLength)
    {
        // we are finished
        printf("%s\n", str);
        return;
    }

    if (ones > 0)
    {
        // put a 1 into the new string
        str[length] = '1';
        recurse(str, length + 1, maxLength, ones - 1);
    }

    if (ones < maxLength - length)
    {
        // there are still spaces for 0s
        // put a 0 into the string
        str[length] = '0';
        recurse(str, length + 1, maxLength, ones);
    }
}

int main()
{
    const int maxLength = 5;
    char buffer[maxLength + 1];
    buffer[maxLength] = 0;

    int ones;
    for (ones = 0; ones <= maxLength; ones++)
    {
        printf("Ones: %i\n", ones);
        recurse(buffer, 0, maxLength, ones);
        printf("\n");
    }

    return 0;
}

The output looks like this:

Ones: 0
00000

Ones: 1
10000
01000
00100
00010
00001

Ones: 2
11000
10100
10010
10001
01100
01010
01001
00110
00101
00011

Ones: 3
11100
11010
11001
10110
10101
10011
01110
01101
01011
00111

Ones: 4
11110
11101
11011
10111
01111

Ones: 5
11111

Finally, unless you really want to/need to learn/use C, I would recommend using C++ because you get really nice features like std::vector and std::set and so many other things which will make your life so much easier. I would have written this completely different in C++.