using recursion to generate all possible bitstrings of length n
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9

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

  1. #1
    Join Date
    Feb 2009
    Posts
    5

    Question 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. #2
    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. #3
    dlorde is offline 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
    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.

  4. #4
    Join Date
    Feb 2009
    Posts
    56

    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
    Quote Originally Posted by dlorde View Post
    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. #5
    Join Date
    Nov 2003
    Posts
    1,405

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

    Quote Originally Posted by IRnick View Post
    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. #6
    dlorde is offline Elite Member Power Poster
    Join Date
    Aug 1999
    Location
    UK
    Posts
    10,163

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

    Quote Originally Posted by yuenqi View Post
    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 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
    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.

  7. #7
    Join Date
    Sep 2008
    Posts
    15

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

    Quote Originally Posted by dlorde View Post
    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 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. #8
    dlorde is offline Elite Member Power Poster
    Join Date
    Aug 1999
    Location
    UK
    Posts
    10,163

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

    Quote Originally Posted by Marie Mih View Post
    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 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.

  9. #9
    Join Date
    Nov 2003
    Posts
    1,405

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

    Quote Originally Posted by Marie Mih View Post
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center