N nested loops

Question

I need to create N nested loops to print all combinations of a binary sequence of length N. I'm not sure how to do this.

Any help would be greatly appreciated. Thanks.

Answer 1

Use recursion. for example in java

public class Foo { public static void main(String[] args) { new Foo().printCombo("", 5); } void printCombo(String soFar, int len) { if (len == 1) { System.out.println(soFar+"0"); System.out.println(soFar+"1"); } else { printCombo(soFar+"0", len-1); printCombo(soFar+"1", len-1); } } } 

prints 00000 00001 00010 ... 11101 11110 11111

Answer 2

You have two options:

• Use backtracking instead.
• Write a program that generates a dynamic program with N cycles and then executes it.

Answer 3

You do not need nested loops for this. You will need one recursive function to print a binary value of length N and a for loop to iterate over all numbers [0 .. (2 ^ N) -1].

The user949300 solution is also very good, but may not work in all languages.

Here's my solution (s), recursive, about twice as slow as iterative:

 #include <stdio.h> #ifdef RECURSIVE void print_bin(int num, int len) { if(len == 0) { printf("\n"); return; } print_bin(num >> 1, len -1); putchar((num & 1) + '0'); } #else void print_bin(int num, int len) { char str[len+1]; int i; str[len] = '\0'; for (i = 0; i < len; i++) { str[len-1-i] = !!(num & (1 << i)) + '0'; } printf("%s\n", str); } #endif int main() { int len = 24; int i; int end = 1 << len; for (i = 0; i < end ; i++) { print_bin(i, len); } return 0; } 

(I tried this myself on a Mac, printing all 24 binary numbers and the terminal froze. But this is probably a poor terminal implementation. :-)

 $ gcc -O3 binary.c ; time ./a.out > /dev/null ; gcc -O3 -DRECURSIVE binary.c ; time ./a.out > /dev/null real 0m1.875s user 0m1.859s sys 0m0.008s real 0m3.327s user 0m3.310s sys 0m0.010s 

Answer 4

I don’t think we need recursion or n nested loops to solve this problem. This could be easily dealt with using bit manipulation.

In C ++ as an example:

 for(int i=0;i<(1<<n);i++) { for(int j=0;j<n;j++) if(i&(1<<j)) printf("1"); else printf("0"); printf("\n"); }