CODEWITHSUNDEEP
javarecursionsetpowerset
Caboose
Caboose

Reputation: 463

Getting a powerset recursively

I want to preface this by saying that this is for a school assignment, so while I want help, it would definitely be preferable to point me in the right direction rather than giving me code to use.

So the assignment is to be able to print out the PowerSet (set of all subsets of a given set) of any given set. I'm moderatly experienced with Java, but recursion is one of my weak points so I'm having trouble visualizing this.

My method returns all subsets which include 'd' and the empty set.

Here's what I have so far:

public static TreeSet<TreeSet<Character>> powerSet(TreeSet<Character> setIn) 
{
    Comparator<TreeSet<Character>> comp = new Comparator<TreeSet<Character>>() 
    {
        @Override
        public int compare(TreeSet<Character> a, TreeSet<Character> b)
        {
            return a.size() - b.size();
        }

    };          
    TreeSet<TreeSet<Character>> temp = new TreeSet<TreeSet<Character>>(comp);                                                                               

    if (setIn.isEmpty()) 
    {
        temp.add(new TreeSet<Character>());
        return temp;
    }

    Character first = setIn.first();
    msg(first);
    setIn.remove(first);
    TreeSet<TreeSet<Character>> setA = powerSet(setIn);
    temp.addAll(setA);  
    for (TreeSet<Character> prox : setA) 
    {
        TreeSet<Character> setB = new TreeSet<Character>(prox);
        setB.add(first);
        temp.add(setB); 
    }
    return temp;
}

Given the set

[a, b, c, d]

this method gives me the set

[[], [d], [c, d], [b, c, d], [a, b, c, d]]

but we know that the PowerSet should be

[[], [a], [b], [c], [d], [a, b], [a, c], [a, d], [b, c], [b, d], [c, d],
 [a, b, c], [a, b, d], [a, c, d], [b, c, d], [a, b, c, d]]

Any help going in the right direction would be greatly appreciated.

EDIT: My problem was a really stupid problem. I forget to properly set up the comparator and it was precluding results. I fixed the comparator to sort correctly without throwing away sets.

Here it is:

  public int compare(TreeSet<Character> a, TreeSet<Character> b)
            {           
                if(a.equals(b))
                    return 0;

                if(a.size() > b.size())
                    return 1;

                return -1;
            }

Upvotes: 1

Views: 776

Answers (2)

Andrei Nicusan
Andrei Nicusan

Reputation: 4623

EXTENSIVE EDIT:

The solution is much simpler than I initially thought. You are doing everything very well except the following: before removing the first element from the set, add the set to the temp set.

Something like this:

 temp.add(setIn);
 Character first = setIn.first();
 msg(first);
 setIn.remove(first);

Upvotes: 2

Leliel
Leliel

Reputation: 156

it looks good so far.

you're building every possible subset that contains the first element this can be extended quite simply to do the same for each element of the initial set. just need to do what you're already doing, but for a different element of the initial set.

that should get you a fair bit closer to the powerset.

Upvotes: 0

Related Questions