using recursion to generate all possible bitstrings of length n

[IRnick]

I'm trying to make a 2d array in java filled with the truth table for n amount of variables

ex. 3 variables will create an array that looks like this

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

i'm having trouble coming up with a recursive algorithm to generate all possible bitstrings.
any help would be appreaciated. thanks

[Peter_B]

I guess this is a homework assignment, otherwise it would be better to use an iterative approach (as a simple iterative method exists for this problem).

In order to do this recursively you just have to work out how you are going to break the problem down into smaller problems. To show you how to do this I have sketched the truth table for 4 variables below:

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

By adding a few delimeters we can see that this list is the same as the 3 variable list repeated twice, firstly proceeded by a 0 and then preceeded by a 1:

0|0 0 0
0|0 0 1
0|0 1 0
0|0 1 1
0|1 0 0
0|1 0 1
0|1 1 0
0|1 1 1
---------
1|0 0 0
1|0 0 1
1|0 1 0
1|0 1 1
1|1 0 0
1|1 0 1
1|1 1 0
1|1 1 1

The 3 variable list is itself two copies of the 2 variable list, preceeded by either 0 or 1:

0 |0 0
0 |0 1
0 |1 0
0 |1 1
-------
1| 0 0
1 |0 1
1 |1 0
1 |1 1

By doing this you can see how to reduce the list for n variables to a simple repetition of the list for (n-1) variables.
The base case, for n=1, is simply:

0
1

Hope this helps you

[IRnick]

I guess this is a homework assignment, otherwise it would be better to use an iterative approach (as a simple iterative method exists for this problem).

In order to do this recursively you just have to work out how you are going to break the problem down into smaller problems. To show you how to do this I have sketched the truth table for 4 variables below:

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

By adding a few delimeters we can see that this list is the same as the 3 variable list repeated twice, firstly proceeded by a 0 and then preceeded by a 1:

0|0 0 0
0|0 0 1
0|0 1 0


0
1

Hope this helps you
wasn't homework. this is what we did


private boolean allCombinations()
{
int firstZero=findZero();
if (firstZero==2)
return false; //all combinations explored
assignment[firstZero]=1;
for (int i=firstZero+1; i<=numVars; i++)
{
assignment[i]=0;
}
return true;
}

private int findZero()
{
for (int i = numVars; i >0; i--)
{
if (assignment[i]==0)
return i;
}//end for
return 2;
}

what is the iterative method you were talking about?

[dannystommen]

A iterative approach is looping through a collectection, and that is exactly what you do when you use a for-loop.

Also, please use code-tags ( [ code] your code here [/ code], but then without the space before 'code')

[Khiem]

Do you mind telling me or us why you choose the recursive when its easier to do with usual iterative ?

[Peter_B]

wasn't homework. this is what we did

private boolean allCombinations()
{
int firstZero=findZero();
if (firstZero==2)
return false; //all combinations explored
assignment[firstZero]=1;
for (int i=firstZero+1; i<=numVars; i++)
{
assignment[i]=0;
}
return true;
}

private int findZero()
{
for (int i = numVars; i >0; i--)
{
if (assignment[i]==0)
return i;
}//end for
return 2;
}

what is the iterative method you were talking about?

What you have presented *is* the iterative method for doing this. Recursion involves a function solving a problem by calling itself to solve subproblems, and combining these to produce the solution for the original problem.

[IRnick]

Do you mind telling me or us why you choose the recursive when its easier to do with usual iterative ?

I didn't think of iterative

[IRnick]

What you have presented *is* the iterative method for doing this.

I thought you meant there was one in the API