CODEWITHSUNDEEP
javaalgorithmbig-o
Shawn
Shawn

Reputation: 7365

Finding a particular Set of SubSets of a PowerSet in an efficient way

I'm trying to find an efficient way to grab a Set of Subsets of a PowerSet.

For example, this works when the set sizes are small:

Set<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(2);
set.add(3);

Set<Integer> set2 = new HashSet<Integer>();
set2.add(3);


Set<Set<Integer>> sets = MyUtils.powerSet(set); //size - 8 SubSets
Set<Set<Integer>> badSets = MyUtils.powerSet(set2); //size - 2 SubSets

//my set of subsets of the powerset
sets.removeAll(badSets) //size - 6 SubSets

However when more elements are added to these sets this does not become practical. Is there another way to do this?

Just friendly reminder of what a PowerSet is:

PowerSet of {a,b,c}:

P(S) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

Upvotes: 2

Views: 599

Answers (4)

Saeed Amiri
Saeed Amiri

Reputation: 22555

If one set is subset of another one (A,B sizes m,n) after removing P(B) from P(A) you have 2n - 2m element, also if B is not a subset of A, again you can assume B'=A intersection with B and again we have similar relation, so numbers are big in all.

for example assume A-B has one element, |P(A)-P(B)| = 2n - 2(n-1) = 2(n-1), for example for n = 40 you can't iterate over all items.

anyway, one way is as bellow:

have a counter of size n in base 2, first set m+1 bit as 1 and all others as 0 then print result, and each time increase counter (by one) and print result upto rich to 2n - 1. which is O(2n - 2m).

Upvotes: 3

Alex Abdugafarov
Alex Abdugafarov

Reputation: 6392

For subtracting one power set from another, deducted power set computataion is redundant. Here is the way to go:

public static <T>void removePowerSet(
        Collection <? extends Collection <T>> powerSet,
        Collection <T> removedComponents){
    Iterator <? extends Collection <T>> powerSetIter = powerSet.iterator();
    while (powerSetIter.hasNext()) {
        Collection <T> powerSetSubset = powerSetIter.next();
        if (removedComponents.containsAll(powerSetSubset)) {
            powerSetIter.remove();
        }
    }
}

This algorithm performs in a polynomial time - O(n2) for a HashSet

Now you can call removePowerSet(sets, set2) or removePowerSet(sets, Arrays.asList(3)) to get the result in your example.

Upvotes: 0

user555045
user555045

Reputation: 64904

Sounds like a job for zero suppressed decision diagrams. They support set-subtraction and creating a powerset of a range of numbers is trivial in ZDD's (and in fact the resulting ZDD has very few nodes). That means that the asymmetric difference will also run fast, because it's on two small ZDD's and it depends only on the size of the ZDD's in nodes, not the size in number of sets they contain. I don't know what you're going to do with it next, but whatever it is, you could always enumerate all sets in the ZDD and put them in an other datastructure.

Upvotes: 1

Thinhbk
Thinhbk

Reputation: 2214

Try another way:

let call set3 = set - set2;

Then Powerset(set) - Poserset(set2) = Powerset(set3) x (Powerset(set)- {});

where x here is Descartes multiple of 2 set.

if set3 has x element, set2 has y element, then with this approach, it's complexity around 2^(x+y), while if try to remove it directly, the complexity is around 2^(x + 2Y).

Hth.

Upvotes: 1

Related Questions