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 the itertools.combinations function to obtain all subsets of our set of interest (the high vowels) of a particular cardinality. To do this, we need a second loop over the output of itertools.combinations at each cardinality is necessary to flatten the sets.

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

{(),
 ('i',),
 ('i', 'u'),
 ('i', 'ʊ'),
 ('i', 'ʊ', 'u'),
 ('u',),
 ('ɪ',),
 ('ɪ', 'i'),
 ('ɪ', 'i', 'u'),
 ('ɪ', 'i', 'ʊ'),
 ('ɪ', 'i', 'ʊ', 'u'),
 ('ɪ', 'u'),
 ('ɪ', 'ʊ'),
 ('ɪ', 'ʊ', 'u'),
 ('ʊ',),
 ('ʊ', 'u')}

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

{frozenset(),
 frozenset({'i', 'ʊ'}),
 frozenset({'ɪ'}),
 frozenset({'ʊ'}),
 frozenset({'i', 'ɪ'}),
 frozenset({'u'}),
 frozenset({'u', 'ɪ'}),
 frozenset({'u', 'ʊ'}),
 frozenset({'i', 'u'}),
 frozenset({'ɪ', 'ʊ'}),
 frozenset({'i'}),
 frozenset({'i', 'u', 'ɪ'}),
 frozenset({'i', 'u', 'ʊ'}),
 frozenset({'i', 'ɪ', 'ʊ'}),
 frozenset({'u', 'ɪ', 'ʊ'}),
 frozenset({'i', 'u', 'ɪ', 'ʊ'})}

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.

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

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

  Returns
  -------
  set[frozenset]
      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)

{frozenset(),
 frozenset({'i', 'ʊ'}),
 frozenset({'ɪ'}),
 frozenset({'ʊ'}),
 frozenset({'i', 'ɪ'}),
 frozenset({'u'}),
 frozenset({'u', 'ɪ'}),
 frozenset({'u', 'ʊ'}),
 frozenset({'i', 'u'}),
 frozenset({'ɪ', 'ʊ'}),
 frozenset({'i'}),
 frozenset({'i', 'u', 'ɪ'}),
 frozenset({'i', 'u', 'ʊ'}),
 frozenset({'i', 'ɪ', 'ʊ'}),
 frozenset({'u', 'ɪ', 'ʊ'}),
 frozenset({'i', 'u', 'ɪ', 'ʊ'})}

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
from itertools import chain

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

powerset(high_vowels)

<itertools.chain at 0x7fbf50a46560>

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)}

{frozenset(),
 frozenset({'i', 'ʊ'}),
 frozenset({'ɪ'}),
 frozenset({'ʊ'}),
 frozenset({'i', 'ɪ'}),
 frozenset({'u'}),
 frozenset({'u', 'ɪ'}),
 frozenset({'u', 'ʊ'}),
 frozenset({'i', 'u'}),
 frozenset({'ɪ', 'ʊ'}),
 frozenset({'i'}),
 frozenset({'i', 'u', 'ɪ'}),
 frozenset({'i', 'u', 'ʊ'}),
 frozenset({'i', 'ɪ', 'ʊ'}),
 frozenset({'u', 'ɪ', 'ʊ'}),
 frozenset({'i', 'u', 'ɪ', 'ʊ'})}

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.

from collections.abc import Generator
from multiprocessing import Process

def natural_numbers() -> 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
N: Generator[int] = natural_numbers()

# this will hang
# powerset(N)

If we want to be able to generate elements of the power set of an infinite set, we will have to do it in a slightly smarter way.

from collections.abc import Iterable

emptyset = frozenset()

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

    Works for both finite and infinite iterables by yielding
    subsets as new elements arrive.

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

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

    seen = {emptyset}

    for r in iterable:
        new = {s | frozenset({r}) for s in seen}
        for n in new:
            yield n
            seen.add(n)

This will still get us the correct result for finite sets.

{s for s in powerset(high_vowels)}

{frozenset(),
 frozenset({'i', 'ʊ'}),
 frozenset({'ɪ'}),
 frozenset({'ʊ'}),
 frozenset({'i', 'ɪ'}),
 frozenset({'u'}),
 frozenset({'u', 'ʊ'}),
 frozenset({'u', 'ɪ'}),
 frozenset({'i'}),
 frozenset({'i', 'u'}),
 frozenset({'i', 'u', 'ɪ'}),
 frozenset({'i', 'u', 'ʊ'}),
 frozenset({'ɪ', 'ʊ'}),
 frozenset({'i', 'ɪ', 'ʊ'}),
 frozenset({'u', 'ɪ', 'ʊ'}),
 frozenset({'i', 'u', 'ɪ', 'ʊ'})}

And it will also work for infinite sets.

N = natural_numbers()

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

frozenset()
frozenset({0})
frozenset({0, 1})
frozenset({1})
frozenset({2})
frozenset({1, 2})
frozenset({0, 2})
frozenset({0, 1, 2})
frozenset({2, 3})
frozenset({0, 2, 3})
frozenset({0, 3})
frozenset({3})
frozenset({0, 1, 2, 3})
frozenset({1, 3})
frozenset({1, 2, 3})
frozenset({0, 1, 3})
frozenset({0, 3, 4})
frozenset({3, 4})
frozenset({0, 1, 4})
frozenset({2, 3, 4})
frozenset({1, 4})
frozenset({1, 2, 4})
frozenset({0, 1, 2, 3, 4})
frozenset({0, 2, 3, 4})
frozenset({0, 4})
frozenset({2, 4})
frozenset({0, 2, 4})
frozenset({1, 2, 3, 4})
frozenset({0, 1, 3, 4})
frozenset({0, 1, 2, 4})
frozenset({1, 3, 4})
frozenset({4})
frozenset({1, 3, 5})
frozenset({4, 5})
frozenset({0, 2, 5})
frozenset({0, 5})
frozenset({0, 3, 4, 5})
frozenset({0, 1, 3, 4, 5})
frozenset({0, 3, 5})
frozenset({0, 4, 5})
frozenset({0, 2, 3, 4, 5})
frozenset({0, 2, 3, 5})
frozenset({1, 2, 3, 4, 5})
frozenset({2, 3, 5})
frozenset({3, 5})
frozenset({3, 4, 5})
frozenset({1, 2, 4, 5})
frozenset({0, 1, 2, 4, 5})
frozenset({0, 1, 4, 5})
frozenset({0, 2, 4, 5})
frozenset({0, 1, 3, 5})
frozenset({2, 3, 4, 5})
frozenset({1, 2, 5})
frozenset({1, 5})
frozenset({1, 4, 5})
frozenset({5})
frozenset({0, 1, 2, 5})
frozenset({1, 3, 4, 5})
frozenset({1, 2, 3, 5})
frozenset({0, 1, 2, 3, 4, 5})
frozenset({2, 4, 5})
frozenset({2, 5})
frozenset({0, 1, 5})
frozenset({0, 1, 2, 3, 5})
frozenset({1, 4, 5, 6})
frozenset({4, 6})
frozenset({2, 3, 5, 6})
frozenset({2, 6})
frozenset({0, 1, 2, 4, 5, 6})
frozenset({0, 2, 4, 6})
frozenset({0, 1, 4, 5, 6})
frozenset({0, 5, 6})
frozenset({0, 2, 3, 6})
frozenset({0, 1, 2, 5, 6})
frozenset({1, 2, 3, 4, 5, 6})
frozenset({0, 3, 4, 6})
frozenset({0, 1, 3, 4, 5, 6})
frozenset({2, 3, 4, 6})
frozenset({4, 5, 6})
frozenset({0, 2, 3, 4, 5, 6})
frozenset({1, 3, 4, 6})
frozenset({1, 2, 3, 4, 6})
frozenset({1, 4, 6})
frozenset({0, 1, 2, 3, 4, 6})
frozenset({2, 4, 6})
frozenset({3, 4, 5, 6})
frozenset({0, 4, 6})
frozenset({1, 3, 4, 5, 6})
frozenset({0, 6})
frozenset({0, 3, 5, 6})
frozenset({0, 2, 6})
frozenset({0, 1, 2, 4, 6})
frozenset({0, 2, 5, 6})
frozenset({0, 3, 6})
frozenset({0, 4, 5, 6})
frozenset({0, 2, 4, 5, 6})
frozenset({3, 4, 6})
frozenset({5, 6})
frozenset({1, 2, 4, 5, 6})
frozenset({2, 4, 5, 6})