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', 'ɪ'),
 ('i', 'ɪ', 'ʊ'),
 ('i', 'ʊ'),
 ('u',),
 ('u', 'i'),
 ('u', 'i', 'ɪ'),
 ('u', 'i', 'ɪ', 'ʊ'),
 ('u', 'i', 'ʊ'),
 ('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({'u', 'ʊ'}),
 frozenset({'i', 'u', 'ʊ'}),
 frozenset({'u', 'ɪ'}),
 frozenset({'i', 'ɪ'}),
 frozenset({'ɪ', 'ʊ'}),
 frozenset({'i', 'ʊ'}),
 frozenset({'ɪ'}),
 frozenset({'i'}),
 frozenset({'ʊ'}),
 frozenset({'u'}),
 frozenset({'i', 'u'}),
 frozenset({'i', 'u', 'ɪ'}),
 frozenset({'u', 'ɪ', 'ʊ'}),
 frozenset({'i', 'ɪ', 'ʊ'}),
 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.

from typing import Set

def powerset(x: set) -> Set[frozenset]:
  return {
      frozenset(subset) 
      for cardinality in range(len(x)+1) 
      for subset in combinations(x, cardinality)
  }

powerset(high_vowels)

{frozenset(),
 frozenset({'u', 'ʊ'}),
 frozenset({'i', 'u', 'ʊ'}),
 frozenset({'u', 'ɪ'}),
 frozenset({'i', 'ɪ'}),
 frozenset({'ɪ', 'ʊ'}),
 frozenset({'i', 'ʊ'}),
 frozenset({'ɪ'}),
 frozenset({'i'}),
 frozenset({'ʊ'}),
 frozenset({'u'}),
 frozenset({'i', 'u'}),
 frozenset({'i', 'u', 'ɪ'}),
 frozenset({'u', 'ɪ', 'ʊ'}),
 frozenset({'i', 'ɪ', 'ʊ'}),
 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 typing 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 0x106193070>

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({'u', 'ʊ'}),
 frozenset({'i', 'u', 'ʊ'}),
 frozenset({'u', 'ɪ'}),
 frozenset({'i', 'ɪ'}),
 frozenset({'ɪ', 'ʊ'}),
 frozenset({'i', 'ʊ'}),
 frozenset({'ɪ'}),
 frozenset({'i'}),
 frozenset({'ʊ'}),
 frozenset({'u'}),
 frozenset({'i', 'u'}),
 frozenset({'i', 'u', 'ɪ'}),
 frozenset({'u', 'ɪ', 'ʊ'}),
 frozenset({'i', 'ɪ', 'ʊ'}),
 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:
    """Initialize a generator for the natural numbers"""
    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 typing import TypeVar, Set, Iterable

T = TypeVar("T")

emptyset = frozenset()

def powerset(iterable: Iterable[T]) -> Set[T]:
    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({'u', 'ʊ'}),
 frozenset({'i', 'u', 'ʊ'}),
 frozenset({'u', 'ɪ'}),
 frozenset({'i', 'ɪ'}),
 frozenset({'ɪ', 'ʊ'}),
 frozenset({'i', 'ʊ'}),
 frozenset({'ɪ'}),
 frozenset({'i'}),
 frozenset({'ʊ'}),
 frozenset({'u'}),
 frozenset({'i', 'u'}),
 frozenset({'i', 'u', 'ɪ'}),
 frozenset({'u', 'ɪ', 'ʊ'}),
 frozenset({'i', 'ɪ', 'ʊ'}),
 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})