CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: using recursion to generate all possible bitstrings of length n

1. Junior Member
Join Date
Feb 2009
Posts
5

## 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

2. Junior Member
Join Date
Feb 2009
Posts
1

## 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 ..

3. Elite Member Power Poster
Join Date
Aug 1999
Location
UK
Posts
10,163

## 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

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

5. _uj
Banned
Join Date
Nov 2003
Posts
1,405

## 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?

6. Elite Member Power Poster
Join Date
Aug 1999
Location
UK
Posts
10,163

## 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 ?

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 open-source 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

7. Banned
Join Date
Sep 2008
Posts
15

## Re: using recursion to generate all possible bitstrings of length n

Originally Posted by dlorde
So don't use it.

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 open-source 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" ?

8. Elite Member Power Poster
Join Date
Aug 1999
Location
UK
Posts
10,163

## Re: using recursion to generate all possible bitstrings of length n

Originally Posted by Marie Mih
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" ?
Either, both, or none, as you like

Oddly enough, it's just a contraction of my real name, Dave Lorde

I blame my parents

Incidentally, is it just a co-incidence that your user name sounds like (is homophonic with) 'marry me' ?

The name of a man is a numbing blow from which he never recovers...
Marshall McLuhan
Last edited by dlorde; February 4th, 2009 at 07:58 AM.

9. _uj
Banned
Join Date
Nov 2003
Posts
1,405

## 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
•

×