[cthomas1489]

I'm looking for some assistance in writing a class that will return an ArrayList of bit strings given a user input length of k using recursion. This is for a homework assignment.

Basically for user input 2, it will return:

00
01
10
11

if 4:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

and so on for any given length k. I have to write the algorithm myself so I can't use any of java's libraries that deal with binary or bits. By thought process of how to go about this is as follow I just don't know how to implement it.

- Get the size of the user input and store it as k
- Create variable of length k that consists of all zero's
- Perform binary addition of +1 over and over until a string of all 1's is achieved

the stub to the class we were given is this:

public static ArrayList<String> bitStrings(int k) {

}

[DimitriV]

So what you mean is that it will return every possible combination of 0's and 1's to form any given number?

[cthomas1489]

Yep pretty much. It'll be returned in a way where I could have it printed like shown above. Would it be beneficial to use a 2D array or is that not needed?

[blackcompe]

One option is to implement your own intToBinaryString method and call it on all integers from 0 to 2^k.

A 2D array isn't needed for this.

Edit: Scratch the permutation idea.

This post has been edited by blackcompe: 14 November 2011 - 06:01 PM

[cthomas1489]

I think I can write an intToBinaryString method rather easily and implement that. The method will convert int to binary and that will be called on 2^k integers. I was trying to figure out a permutation approach because really this does need to be done recursively and that first approach seems like it can be done without calling itself over and over.

[blackcompe]

Oh yeah, I forgot about the recursive part. Well, in that case you do want to take a permutation-like approach.

This post has been edited by blackcompe: 14 November 2011 - 06:17 PM

[pbl]

the Integer class has a toString() method that receives as parameter an int and the radix so a simple for() loop will do the job

[cfoley]

Whenever you're doing recursion, you should think about the base cases first. What value or values of k make the answer simple enough to write down without even thinking. Those are your base cases. Then think about the recursive cases. What do you have to do to the base case to build the next one up?

I'll give you one base case. when k=0, the answer is an empty list. There is one more base case.

I think it's an exercise for class there.

This post has been edited by cfoley: 14 November 2011 - 06:49 PM

[cthomas1489]

When k =1? which is just:
0
1

So from k=0 to k=1 we go from 2^0 (empty) lines to 2^1 lines (2 lines, one 0, one 1).

To go from k=1 to k=2 we copy k=1 so theres 4 lines (0 then 1 then 0 then 1) and add 0's before the first set and 1's to the second set to get:

00
01
10
11

To go from k=2 to k=3 we copy k=2 to so theres 8 lines and add the right about of 0's and 1's (4 each) before.

000
001
010
011
100
101
110
111

So basically the recursive part is calling the previous k over and over again...? am I on the right track?

[baavgai]

cthomas1489, on 15 November 2011 - 03:10 PM, said:

So basically the recursive part is calling the previous k over and over again...? am I on the right track?

Yes. The k==1, or k<=1 to be safe, creates and returns an ArrayList with two entries. This is your recursive terminator. The rest of the methods take the result of the prior method and essentially double the result, adding "0" first, then "1".

I don't see a clean way to reuse the return ArrayList, so don't bother. Make a fresh one to return and fill it from the prior.

That's about it. Hope I didn't give too much away. Good luck.

[pbl]

cthomas1489, on 15 November 2011 - 03:10 PM, said:

So basically the recursive part is calling the previous k over and over again...? am I on the right track?

Not really This is recurtion on disguise

Actually if you want a method that recursively returns

"0\n1"
"00\n01\n10\n11"
"000\n001\n010\n011\n100\n101\n110\n111"

I would unserstand how recursion could be some how involved
In your case, just the fact that you populate a single ArrayList (even if you pass it as parameter) is just doing calling the same method to call the same method, nothing to do with recursion

But baavgai might have his words to say

This post has been edited by pbl: 15 November 2011 - 02:06 PM
Reason for edit:: Edited: what did I said :)

[cfoley]

Yes, that's what I was getting at cthomas.

Pbl, the method I was intending doesn't populate a single array list, rather it returns an array list. Therefore, calling it with k=4 will generate 4 array lists in the course of the calculation. It may be horrendously inefficient, but it does fit the spec.

[cthomas1489]

Baavgai and cfoley thanks! I'll be able to work on it soon and will post what I have, hopefully working. Yeah no worries about being efficient or fitting a certain runtime requirement. Just as long as it uses recursion.

[cfoley]

Quote

The k==1, or k<=1 to be safe

I'd probably go for k==0 as an empty list and k<0 either throwing an exception or ignored if it was just a demo. Your mileage may vary.

[cthomas1489]

Hmm seems I overlooked having java.math.BigInteger imported so I can use those methods too. Didn't notice that.

BigInteger

Not sure how I can use that but helpful

This post has been edited by cthomas1489: 15 November 2011 - 05:35 PM