N nested for-loops

Question

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

Any help would be greatly appreciated. Thanks.

It is likely to be Java. I only need to work out the pseudo code. I can stick it into any language once I have the solution — BluffTrout, Nov 14 '11 at 18:45
Like this? http://stackoverflow.com/questions/4928297/all-permutations-of-a-binary-sequence-x-bits-long/4928350#4928350 — Josh Bleecher Snyder, Nov 14 '11 at 18:48
I'm not too familiar with Python. I'm not sure what you answer to that question is doing. Are you hard-coding all the possibilities? — BluffTrout, Nov 14 '11 at 19:19

score 7 · Accepted Answer · answered Nov 14 '11 at 18:54

7

Use recursion. e.g., 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);
      }         
   }
}

will print 00000 00001 00010 ... 11101 11110 11111

answered Nov 14 '11 at 18:54

user949300

15,364
7
35
66

This might work. I'll try and implement it into my algorithm and get back to you. – BluffTrout Nov 14 '11 at 19:23
1

@BluffTrout: It *will* work because recursion is how you solve this problem. – Ed S. Nov 14 '11 at 21:31
@BluffTrout Depending on the criteria you use to determine if it is a feasible solution, you could add a check at the start of printCombo(), e.g. `if (notFeasable(soFar)) return;` – user949300 Nov 15 '11 at 00:47
This has worked great. I have managed to change it to fit what I was looking for. Thanks for everyone's help :) – BluffTrout Nov 15 '11 at 12:14

score 0 · Answer 2 · answered Nov 14 '11 at 18:42

0

You have two options here:

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

answered Nov 14 '11 at 18:42

Tudor

61,523
12
102
142

I don't think Backtracking is correct, since that only applies when some solutions are impossible. I think what you meant was recursion. – user949300 Nov 14 '11 at 18:46
1

Yes, actually I meant the recursive backtracking. Also you can use backtracking with an empty validation function i.e. accept any generated solution. – Tudor Nov 14 '11 at 18:47

onemasse · Answer 3 · 2011-11-14T22:00:35.427

You don't need any nested loops for this. You 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].

user949300's solution is also very good, but it might not work in all languages.

Here's my solution(s), the recursive one is approximately twice as slow as the iterative one:

#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 binary numbers of length 24 and the terminal froze. But that 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

Ouch. Yeah that will probably not work. In terms of the program that I am creating, I need to step through each combination and see if it's a feasible solution to another problem. It doesn't neccessarily, need to compute all combinations at once. — BluffTrout, Nov 14 '11 at 19:46
I don't think there's any problem with the algorithm as such but with Terminal.app's ability to handle the history. — onemasse, Nov 14 '11 at 19:52
So for large N do it more explicitly via a single for-next loop and, in Java, Integer.toString(theValue, 2);. Same idea as [presented here](http://stackoverflow.com/questions/4928297/all-permutations-of-a-binary-sequence-x-bits-long/4928336#4928336) — user949300, Nov 14 '11 at 20:01

score 0 · Answer 4 · answered Nov 14 '11 at 22:25

I don't think we need recursion or n nested for-loops to solve this problem. It would be easy to handle this 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");
}

N nested for-loops

4 Answers4