Generate binary sequence

Question

I want to create a permutation of a row of 5 0s, followed by a permutation of 4 0s and one 1, and then a permutation 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; } } } } 

Thus, the conclusion

 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 

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

Answer 1

The following is one approach. This solution requires O (n) space, and O (n) time is required for each output line.

 #include <stdio.h> #include <stdlib.h> char *buf; // Print combinations of m 1 in a field of n 0/1 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 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 can use such a recursive function - you do not need to print the result at the end, you can add it to the list, etc.

The function works starting from an empty line. At each step, you add one more character - in this case you add either 0 or 1 .

If 1 added, we will take this into account by decreasing the ones value on the next function call. (In a more general case, you can transfer a list of all the elements that you want to rearrange - then the process should select from this list, add it to your permutation and remove it from the list. Repeat this until the list is empty and you move all the elements to list.)

When the string reaches the desired length, we are done and we will 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 result is as follows:

 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, if you really don't want / shouldn't 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 that will make your life a lot easier, I would write this completely different in C ++.