How to Get All Subsets of a Set - Powerset

How to get all subsets of a set? (powerset)

The Python itertools page has exactly a powerset recipe for this:

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Output:

>>> list(powerset("abcd"))
[(), ('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')]

If you don't like that empty tuple at the beginning, you can just change the range statement to range(1, len(s)+1) to avoid a 0-length combination.

How to find all subsets of a set in JavaScript? (Powerset of array)

Here is one more very elegant solution with no loops or recursion, only using the map and reduce array native functions.

const getAllSubsets =       theArray => theArray.reduce(        (subsets, value) => subsets.concat(         subsets.map(set => [value,...set])        ),        [[]]      );
console.log(getAllSubsets([1,2,3]));

How can I find all the subsets of a set, with exactly n elements?

itertools.combinations is your friend if you have Python 2.6 or greater. Otherwise, check the link for an implementation of an equivalent function.

import itertools
def findsubsets(S,m):
    return set(itertools.combinations(S, m))

S: The set for which you want to find subsets

m: The number of elements in the subset

create a list of all the subsets of a given list in python 3.x

You can use itertools.combinations to get the combinations:

>>> import itertools
>>> xs = [1, 2, 3]

>>> itertools.combinations(xs, 2)  # returns an iterator
<itertools.combinations object at 0x7f88f838ff48>
>>> list(itertools.combinations(xs, 2))  # yields 2-length subsequences
[(1, 2), (1, 3), (2, 3)]


>>> for i in range(0, len(xs) + 1):  # to get all lengths: 0 to 3
...     for subset in itertools.combinations(xs, i):
...         print(list(subset))
... 
[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]

combining with list comprehension, you will get what you want:

>>> [list(subset) for i in range(0, len(xs) + 1)
                  for subset in itertools.combinations(xs, i)]
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Generating all the elements of a power set

The problem is in your hasNext. You have i++ < subsets there. What happens is that since hasNext is called once from next() and once more during the iteration for (Set<Integer> subset : pSet) you increment i by 2 each time. You can see this since

for (Set<Integer> subset : pSet) {

}

is actually equivalent to:

Iterator<PowerSet> it = pSet.iterator();
while (it.hasNext()) {
    Set<Integer> subset = it.next();
}

Also note that

if (bitSet.cardinality() == 0) {
    return subset;
}

is redundant. Try instead:

@Override
public boolean hasNext() {
    return i <= subsets;
}

@Override
public Set<E> next() {
    if (!hasNext()) {
        throw new NoSuchElementException();
    }
    Set<E> subset = new TreeSet<E>();
    BitSet bitSet = BitSet.valueOf(new long[] { i });
    for (int e = bitSet.nextSetBit(0); e != -1; e = bitSet.nextSetBit(e + 1)) {
        subset.add(ary[e]);
    }
    i++;

    return subset;
}

How to Get All Subsets of a Set - Powerset