
February 1st, 2009, 03:08 AM
#1
using recursion to generate all possible bitstrings of length n
I'm trying to make a 2d array 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 appreciated. thanks

February 1st, 2009, 03:25 AM
#2
Re: using recursion to generate all possible bitstrings of length n
hellow ..
instead of 2d array .. if u transform the problem in lists .(linklists ) problem will be solved easily .. i m doing it .. and will send u the solution if it works ..

February 1st, 2009, 09:11 AM
#3
Re: using recursion to generate all possible bitstrings of length n
Do you have to use recursion? For a truth table like this, each row is just the binary value of its row index:
0  0 0 0
1  0 0 1
2  0 1 0
3  0 1 1
4  1 0 0
5  1 0 1
6  1 1 0
7  1 1 1
But for a more general solution, recursion can be useful. One simple recursive solution is to pass the array of items and a length value (starting at the array length) to a recursive method that iterates over the array up to the length value, and for each index it swaps the item at the index with the one at length  1, then calls itself, passing the array and length  1, then repeats the previous swap.
If this is tricky to grasp, it might help to step through the algorithm on paper.
The hardest part of the software task is arriving at a complete and consistent specification, and much of the essence of building a program is in fact the debugging of the specification...
F. Brooks
Please use [CODE]...your code here...[/CODE] tags when posting code. If you get an error, please post the full error message and stack trace, if present.

February 3rd, 2009, 09:16 PM
#4
Re: using recursion to generate all possible bitstrings of length n
How about converting int to binary string then separate ? This is obviously not a smart solution since you work with low level binary digit which later on works with string. It consumes so much resources and longer time complexity
Originally Posted by dlorde
But for a more general solution, recursion can be useful.
You mind explaining in details of the usefullness you find in this problem, don't you ?
One simple recursive solution is to pass the array of items and a length value (starting at the array length) to a recursive method that iterates over the array up to the length value, and for each index it swaps the item at the index with the one at length  1, then calls itself, passing the array and length  1, then repeats the previous swap.
If this is tricky to grasp, it might help to step through the algorithm on paper.
That sounds descriptive but I am skeptical of its practicality. You care of posting some code for everyone to watch ?
The hardest part of the software task is arriving at a complete and consistent specification, and much of the essence of building a program is in fact the debugging of the specification...
F. Brooks
I see this kind of memos in all of your posts, could you stop borrow people's quotes and spread them like plague in all of the thread you join in? If you want to show people your views, then write yourself one after each post. he color and people's words are beautiful but your act of borrowing looks like a formal art of stealing in disguise. Thanks

February 4th, 2009, 07:14 AM
#5
Re: using recursion to generate all possible bitstrings of length n
Originally Posted by IRnick
i'm having trouble coming up with a recursive algorithm to generate all possible bitstrings.
Does this mean you had no problems with an iterative solution?

February 4th, 2009, 07:33 AM
#6
Re: using recursion to generate all possible bitstrings of length n
Originally Posted by yuenqi
How about converting int to binary string then separate ? This is obviously not a smart solution since you work with low level binary digit which later on works with string. It consumes so much resources and longer time complexity
So don't use it.
You mind explaining in details of the usefullness you find in this problem, don't you ?
Your meaning isn't clear.
That sounds descriptive but I am skeptical of its practicality. You care of posting some code for everyone to watch ?
If you don't think you can write the code yourself, you can find several examples online if you search. I didn't invent the algorithm. If you don't feel it's practical use another.
I see this kind of memos in all of your posts, could you stop borrow people's quotes and spread them like plague in all of the thread you join in?
No. I put them there for amusement and interest. That's what quotes are for. Most opinions of them are positive. If you don't like them, you don't have to read them, or you can just skip my posts altogether.
If you want to show people your views, then write yourself one after each post. he color and people's words are beautiful but your act of borrowing looks like a formal art of stealing in disguise. Thanks
I have put my own words there at various times, but I'm no great wordsmith. I think you'll find quoting is generally encouraged as long as proper attribution is given  much like opensource licensing
Every human being has a right to hear what other wise human beings have spoken to him. It is one of the Rights of Men; a very cruel injustice if you deny it to a man!
Thomas Carlyle
Please use [CODE]...your code here...[/CODE] tags when posting code. If you get an error, please post the full error message and stack trace, if present.

February 4th, 2009, 07:41 AM
#7
Re: using recursion to generate all possible bitstrings of length n
Originally Posted by dlorde
So don't use it.
Your meaning isn't clear.
If you don't think you can write the code yourself, you can find several examples online if you search. I didn't invent the algorithm. If you don't feel it's practical use another.
No. I put them there for amusement and interest. That's what quotes are for. Most opinions of them are positive. If you don't like them, you don't have to read them, or you can just skip my posts altogether.
I have put my own words there at various times, but I'm no great wordsmith. I think you'll find quoting is generally encouraged as long as proper attribution is given  much like opensource licensing
Every human being has a right to hear what other wise human beings have spoken to him. It is one of the Rights of Men; a very cruel injustice if you deny it to a man!
Thomas Carlyle
Yes, you are right. Your posts to me are all great, and I like to read all of them.
You should not care about that member of sick chinese regime.
I find either the iterative approach or recursive one are just so fine to solve this problem. Time complexity probably is the same.
By the way you have the most special username among many in CG. Does it mean "a lord of d's" or "a super d" ?

February 4th, 2009, 08:49 AM
#8
Re: using recursion to generate all possible bitstrings of length n
Last edited by dlorde; February 4th, 2009 at 08:58 AM.
Please use [CODE]...your code here...[/CODE] tags when posting code. If you get an error, please post the full error message and stack trace, if present.

February 5th, 2009, 03:09 AM
#9
Re: using recursion to generate all possible bitstrings of length n
Originally Posted by Marie Mih
I find either the iterative approach or recursive one are just so fine to solve this problem. Time complexity probably is the same.
Well, the lowest complexity is O(2^N) where N is the number of bits (in this case 3).
The standard iterative algoritm is to use a number of nested loops, one for each bit (in this case there would be 3). This can easily be turned into a recursive algorithm with the same complexity. In that case the recursive method, containing one loop, calls itself to the wanted depth (in this case 3).
So for a fixed N (like 3) you're correct. Both algorithms are "just so fine". But if you want N to be easily variable the recursive version is better. You just change N to another number. In the iterative version you need to modify the code so the number of nested loops corresponds to N.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
