Finding a powerset from a linked list

Question

I am looking for some help with my Java programming assignment. Using a linked list, I need to print out its power set. For example, the set {1,2,3} should print out {{},{1}{1,2}{1,3}{1,2,3}{2}{2,3}{3}}. The number of elements in the power set is 2^n. This needs to be done by calling HeadNode.PrintPowerSet();
where HeadNode is the first element in the linked list. I have tried a few things and nothing is working that well. I think the best way to do it would be to call the method recursively until the end sentinel is reached and then work backwards, adding the elements that are left. Sorry I can't post more code or more ideas because nothing I have tried has worked that well. Thanks in advance.

EDIT: This is the non working code. It returns the set {{1,2,3}{2,3}{3}}

public RSet powerSet() 
{
    if (this == EMPTY_SET)
        return EMPTY_SET;

    RSet q = new RSet();
    if (q != EMPTY_SET)
        q.next = next.powerSet();
    q = new RSet(this, n, q.next);

    return q;
}

EMPTY_SET is the end sentinel. I've tried writing it out by hand. It helps but I still can't get it. Also this class, RSet, is essentially just a linked list node.

[This answer](http://stackoverflow.com/a/1670871/828193) does it using a `Set`. I guess you could easily adapt it to use a `LinkedList` — user000001, Feb 11 '13 at 18:20
Hint: Insert a empty element inside the list..so you will have `n + 1` elements. Then make a recursive function that iterate through all elements in list (including empty one) and it finds all three possibles combination. For example: {Empty, Empty, 1} will be {1}.. — Shivam, Feb 11 '13 at 18:21
Before attempting code, work the problem by hand, and try to write clear human-readable instructions. Next, turn those instructions into code comments. Finally, fill in the code. That separates thinking about how to solve the problem from dealing with unfamiliar language issues. — Patricia Shanahan, Feb 11 '13 at 18:32

Andrew Mao · Answer 1 · 2013-02-11T19:35:11.730

1

Just iterate all the numbers from 0 to 2^n - 1. Each defines an element of the power set:

The list defines a fixed index on your set. For each number, create a new set. Considering the number in its binary format, add the item in the original set at index i to the set if the bit at index i is 1 and don't add it otherwise.

Then, for each number you will have a set that is an element of the power set.

int n = list.size();

Set<Set<T>> powerSet = new HashSet<Set<T>>();

for( long i = 0; i < (1 << n - 1); i++) {
    Set<T> element = new HashSet<T>();
    for( int j = 0; j < n; j++ )
        if( (i >> j) % 2 == 1 ) element.add(list.get(j));
    powerSet.add(element); 
}

return powerSet;

edited Feb 11 '13 at 19:35

answered Feb 11 '13 at 18:29

Andrew Mao

35,740
23
143
224

This set can have strings or any random number. I just gave a simple example. – Jeff Feb 11 '13 at 18:36
Yes, the algorithm I described will work for any type of object. – Andrew Mao Feb 11 '13 at 18:41
I do appreciate it but for this assignment we are not allowed to use Set or HashSet. It must be done with this class and recursively. – Jeff Feb 11 '13 at 19:20
You didn't mention that in your question at all. We have no idea what an `RSet` is supposed to be. – Andrew Mao Feb 11 '13 at 19:29
You're right and I apologize. I'm not very familiar with Java yet and I didn't know that Set was a Java class. I assumed since my class is called RSet it would be a little more apparent but I suppose I was wrong. Sorry for the assumption. – Jeff Feb 11 '13 at 20:33

Finding a powerset from a linked list

1 Answers1