Recursively print Binary subsets of an ArrayList

Question

So I've been wracking my brain over this for a while and, while the code works, it prints it in the absolute wrong order. I feel like I'm missing something so I could use an extra pair of eyes.

void recursiveBitPatterns(ArrayList<String> subsets, int n)
{
    if (n==1)
    {
        subsets.add("0");
        subsets.add("1");
        return;
    }
    recursiveBitPatterns(subsets, n-1);
    int asize = subsets.size();
    for(int i=0; i<asize; i++)
    {
        String nsub = subsets.get(i);
        subsets.set(i, nsub +"0");
        subsets.add(nsub + "1");
    }
}

It seems to be setting the second element of the arraylist to 1 but not overwriting it in the loop.

This prints:

000 100 010 110 001 101 011 111

Any help would be appreciated

What is the code supposed to be doing? What input generated that output and what output did you expect? — Ted Hopp
– Ted Hopp, Commented Oct 31, 2014 at 20:50
@VitJaybird Already I understood what you want to show. Already I modified you code, look below. — SkyMaster
– SkyMaster, Commented Oct 31, 2014 at 22:20

SkyMaster · Accepted Answer · 2014-10-31 22:16:03Z

0

You code would look like.

void recursiveBitPatterns(ArrayList<String> subsets, int n)
{
    if (n==1)
    {
        subsets.add("0");
        subsets.add("1");
        return;
    }
    recursiveBitPatterns(subsets, n-1);
    int asize = subsets.size();
    for(int i=0; i<asize; i++)
    {
        String nsub = subsets.get(i);
        subsets.set(i, "0" + nsub);
        subsets.add("1" + nsub);
    }
}

This prints:

000 001 010 011 100 101 110 111

answered Oct 31, 2014 at 22:16

SkyMaster

1,3231 gold badge8 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Vit Jaybird Over a year ago

Thank you! I figured I just had a small issue in my code. This helps a lot!

AlexITC · Accepted Answer · 2014-10-31 21:21:28Z

0

As far as I read in your code you are trying to generate all possible subsets from a set of N elements.

let subsets to be the arraylist where the subsets will be stored.

void gen(int N, int subset)  {
    if ( N < 0 ) {
        subsets.add( Integer.toBinaryString(subset) );
        return;
    }

    gen(N - 1, subset);
    gen(N - 1, subset | (1 << N) );
}

call it:

gen( sizeOfSet - 1, 0 );

answered Oct 31, 2014 at 21:21

AlexITC

1,0841 gold badge11 silver badges22 bronze badges

Collectives™ on Stack Overflow

Recursively print Binary subsets of an ArrayList

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related