Power Sets

The set of all subsets of a set is its power set.

\[\mathcal{P}(A) = 2^A = \{X \mid X \subseteq A\}\]

For example, for the set \(\{\text{i}, \text{u}, \text{ə}\}\), we have:

\[\mathcal{P}(\{\text{i},\text{u},\text{ə}\}) = 2^{\{\text{i},\text{u},\text{ə}\}} = \{\emptyset, \{\text{i}\}, \{\text{u}\}, \{\text{ə}\}, \{\text{i}, \text{u}\}, \{\text{u},\text{ə}\}, \{\text{i},\text{ə}\}, \{\text{i}, \text{u}, \text{ə}\}\}\]

To obtain the power set of some set, we can loop through all possible subset cardinalities and use itertools.combinations to obtain every subset of each cardinality. The second loop below flattens those groups of combinations into one set.

from itertools import combinations

high_vowels: set[str] = {'u', 'ʊ', 'i', 'ɪ'}

powerset_of_high_vowels = {subset 
                           for cardinality in range(len(high_vowels)+1) 
                           for subset in combinations(high_vowels, cardinality)}

powerset_of_high_vowels

One slightly weird thing about this output is that the set we get has tuples as elements. For most purposes, this result is fine, but sometimes we want the elements to themselves be sets, so we can do set operations on them easily. The issue is that, as we’ve already seen, sets can’t be elements of sets in Python. This is a case where we need frozensets.

powerset_of_high_vowels = {frozenset(subset) 
                           for cardinality in range(len(high_vowels)+1) 
                           for subset in combinations(high_vowels, cardinality)}

powerset_of_high_vowels

So if we wanted to be able to take the power set of anything we can represent in python as a set, we could wrap this comprehension in a function.

from collections.abc import Hashable

def powerset[T: Hashable](x: set[T]) -> set[frozenset[T]]:
    """Compute the power set of a finite set.

  Parameters
  ----------
    x : set[T]
        The set to take the power set of.

  Returns
  -------
    set[frozenset[T]]
        All subsets of the input as frozensets.
    """
    return {
        frozenset(subset)
        for cardinality in range(len(x) + 1)
        for subset in combinations(x, cardinality)
    }

powerset(high_vowels)

Alternatively, we can use the following itertools recipe. The main difference here is that we don’t have the explicit for loop over subsets of a particular cardinality, which we needed for the purposes of flattening sets. That’s what itertools.chain.from_iterable does for us. This returns an itertools.chain object, which you can treat as a generator.

from collections.abc import Iterable, Iterator
from itertools import chain

def powerset[T](iterable: Iterable[T]) -> Iterator[tuple[T, ...]]:
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

powerset(high_vowels)

To get a set of frozensets, we need to some explicit type casting (so we don’t really avoid the second for loop…).

{frozenset(subset) for subset in powerset(high_vowels)}

Note that the thing we’re taking the power set of needs to be of finite size in both implementations–i.e. it can’t be a generator that runs forever. To see this, let’s create a generator for the natural numbers using yield statements. If we create a generator by calling natural_numbers with no arguments, it would run forever. (Below I break it after 10 iterations.)

And if I pass this generator (an iterable) to powerset, it will hang.

def natural_numbers() -> Iterator[int]:
    """Yield the natural numbers starting from 0.

    Yields
    ------
    int
        The next natural number.
    """
    i = 0
    while True:
        yield i
        i += 1

# initialize a generator of the natural numbers
naturals: Iterator[int] = natural_numbers()

# this will hang
# powerset(N)

If we want to generate the finite subsets of an infinite set, we can do it incrementally. This qualification matters: the power set of a countably infinite set is uncountable, so no generator indexed by the natural numbers can enumerate all of it. The diagonal argument in the section on languages establishes exactly this limitation.

def powerset[T: Hashable](iterable: Iterable[T]) -> Iterator[frozenset[T]]:
    """Generate power set elements incrementally.

    For a finite iterable, yields its full power set. For an infinite
    iterable, yields exactly its finite subsets.

    Parameters
    ----------
    iterable : Iterable[T]
        The iterable to take the power set of.

    Yields
    ------
    frozenset[T]
        Subsets of elements seen so far.
    """
    emptyset: frozenset[T] = frozenset()
    yield emptyset

    seen_subsets = {emptyset}
    seen_elements: set[T] = set()

    for r in iterable:
        if r in seen_elements:
            continue

        new = {s | frozenset({r}) for s in seen_subsets}
        seen_elements.add(r)
        seen_subsets |= new

        yield from new

So how do we know this generator gets exactly the subsets we want? The main thing to keep track of is what happens after the loop consumes a finite prefix of the input. At that point, seen_elements is the set of distinct values in the prefix, and seen_subsets should be exactly its power set. This is our stage invariant.

Start with the empty prefix. seen_elements is empty, and seen_subsets contains only emptyset, so the invariant holds. Now suppose it holds for an arbitrary prefix. If the next value \(r\) has appeared before, skipping it leaves both sets unchanged, as required. Otherwise, every subset of the enlarged value set falls into exactly one of two cases: (i) it excludes \(r\) and is already in seen_subsets; or (ii) it includes \(r\) and can be written uniquely as \(s\cup\{r\}\) for some old subset \(s\). The set comprehension called new constructs exactly the second group. Thus, the update preserves the invariant even when the input iterable contains duplicates.

If the input is finite, the loop eventually consumes every element. At that point the invariant says that seen_subsets is the full power set, so this gets us the correct result for finite sets.

{s for s in powerset(high_vowels)}

The duplicate case is a useful regression test: the iterable ['a', 'a', 'b'] denotes the same finite set as ['a', 'b'], so it must yield four subsets exactly once.

duplicate_test = list(powerset(['a', 'a', 'b']))
assert len(duplicate_test) == 4
assert set(duplicate_test) == {
    frozenset(), frozenset({'a'}),
    frozenset({'b'}), frozenset({'a', 'b'}),
}

For an infinite input, the same invariant yields a more limited conclusion. Fix an arbitrary finite subset \(T\) of the input. Every member of \(T\) occurs after some finite number of iterations, so once the last of them has arrived, the construction yields \(T\). Conversely, every yielded subset was constructed at a finite stage and is thus finite. Thus, the generator enumerates exactly the finite subsets.

It cannot yield an infinite subset such as the even natural numbers: no finite stage has seen all of that subset’s members. The code below thus illustrates an enumeration of the finite subsets of \(\mathbb{N}\), not of all \(2^{\mathbb{N}}\).

naturals = natural_numbers()

for i, s in enumerate(powerset(naturals)):
    if i < 100:
        print(s)
    else:
        break