Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generate Binary Sequence

Tags:

c

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?

like image 831
user12290 Avatar asked May 28 '13 23:05

user12290


1 Answers

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;
}
like image 179
Gene Avatar answered Sep 19 '22 05:09

Gene