Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 68 ยท Sets, Relations and Functions

Power Sets and Cartesian Products

Generate power sets and understand 2^n growth, build ordered pairs and Cartesian products with itertools, and enumerate the partitions of a set in Python.

With set operations you can combine two sets into another set of the same kind. This lesson introduces two ways of building new kinds of sets from old ones. The power set collects all subsets of a set. The Cartesian product collects all ordered pairs, one element from each of two sets. A third idea, the partition, slices a set into non-overlapping pieces.

Each of them has a simple size formula and a short Python recipe. Together they are the raw material for relations, functions, graphs and counting, so it is worth getting comfortable with how fast they grow.

The power set

The power set of S, written P(S) or 2^S, is the set of all subsets of S, including the empty set and S itself. For S = {a, b} it is {โˆ…, {a}, {b}, {a, b}}: four subsets.

Why is it also written 2^S? Building a subset means going through the elements and making one yes-or-no decision for each: in or out. With n elements that is n independent two-way choices, so there are 2 ร— 2 ร— ... ร— 2 = 2โฟ subsets. This gives the fundamental size rule:

|P(S)| = 2^|S|

The same decision picture suggests an elegant way of generating all subsets: count from 0 to 2โฟ - 1 in binary and treat each bit as the in/out choice for one element. Python's itertools.combinations offers another route: collect all combinations of size 0, then 1, then 2, and so on.

Python Two ways to generate a power set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both methods produce the same eight subsets. We use frozenset for the subsets because ordinary sets cannot be elements of another set.

Exponential growth

Because the size doubles with every extra element, power sets become impossible to enumerate quickly. Ten elements give 1,024 subsets, twenty give over a million, and fifty give more than a quadrillion. Whenever an algorithm loops over "all subsets", it is exponential, which is why problems like the subset-sum problem and the traveling salesman problem are hard.

Python How fast does 2^n grow?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sum in the last lines previews a fact from Binomial Theorem and Pascal's Triangle: the numbers of subsets of each size add up to 2โฟ.

Ordered pairs and Cartesian products

An ordered pair (a, b) cares about order: (1, 2) is different from (2, 1), unlike the set {1, 2} which is identical to {2, 1}. Two ordered pairs are equal only if both first components match and both second components match. In Python, a tuple is an ordered pair (or, with more entries, an n-tuple).

The Cartesian product A ร— B is the set of all ordered pairs (a, b) with a โˆˆ A and b โˆˆ B. Its size follows the multiplication rule:

|A ร— B| = |A| ยท |B|

Think of a menu with 3 mains and 4 desserts: there are 12 two-course meals. The product is not commutative (A ร— B and B ร— A hold different pairs unless A = B or one is empty) and it is not associative in the strict sense, though the difference between (A ร— B) ร— C and A ร— B ร— C rarely matters in practice.

Products of more than two sets give triples and longer tuples, and the n-fold product of a set with itself is written Aโฟ. The plane โ„ ร— โ„ is the most famous Cartesian product, after Renรฉ Descartes whose name it carries.

Building bigger sets

Power set All subsets. Size 2 to the n.
Product All ordered pairs. Size |A| times |B|.
Partition Non-overlapping pieces that cover the set.

Two of the three grow very fast.

1 / 2

Python's itertools.product does exactly this: it yields the tuples of the product, and the repeat argument builds Aโฟ.

Python Cartesian products with itertools

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A product with an empty set is empty, matching |A| ยท 0 = 0. The repeat=3 example enumerates all binary strings of length 3, the same list of 8 patterns you would see as the rows of a truth table with three variables.

Partitions

A partition of a set S splits it into non-empty, pairwise disjoint subsets, called blocks or parts, whose union is S. Three conditions to check: no block is empty, no two blocks overlap, and together the blocks cover everything. For S = {1, 2, 3} the partitions are:

  • {1, 2, 3} (one block)
  • {1, 2}, {3}
  • {1, 3}, {2}
  • {2, 3}, {1}
  • , {2}, {3} (three blocks)

That makes five. The number of partitions of an n-element set is the Bell number, which begins 1, 1, 2, 5, 15, 52, 203. Partitions matter because they describe how an equivalence relation chops a set into classes, which you will meet in Equivalence Relations and Partial Orders.

A neat recursive way to generate partitions: take the first element and either put it in a block of its own or insert it into one of the blocks of a partition of the remaining elements.

Python Enumerating the partitions of a set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The final line counts the partitions for set sizes 0 to 7, and the counts are the Bell numbers 1, 1, 2, 5, 15, 52, 203, 877. They grow faster than any fixed power of 2 but more slowly than n!. Closed formulas for them come from Stirling numbers, which you will meet in Advanced Counting.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many subsets does a set with 8 elements have?

    Each of the 8 elements is either in or out of a subset, giving 2^8 = 256 subsets, including the empty set and the whole set.
  2. 2. If |A| = 3 and |B| = 5, how many elements does A ร— B have?

    By the product rule, each of the 3 choices from A pairs with each of the 5 choices from B, giving 3 ยท 5 = 15 ordered pairs.
  3. 3. Which is true about A ร— B and B ร— A for non-empty sets with A โ‰  B?

    (a, b) and (b, a) are different ordered pairs, so the products differ as sets, but both have |A| ยท |B| elements.
  4. 4. Which collection is a partition of {1, 2, 3, 4}?

    The blocks {1, 4} and {2, 3} are non-empty, disjoint and cover all four elements. The first overlaps in 2, the second contains an empty block, and the last misses 4.
  5. 5. Which Python call builds the list of all binary strings of length 4 as tuples?

    product with repeat=4 is the fourfold Cartesian product {0,1}^4, which has 2^4 = 16 tuples. Combinations and permutations of two items cannot pick four of them.

Summary

  • The power set P(S) contains all subsets of S and has 2^|S| elements, because each element is in or out.
  • Enumerate subsets with bit masks or itertools.combinations; the exponential growth makes brute-force over subsets feasible only for small n.
  • The Cartesian product A ร— B holds all ordered pairs and has |A| ยท |B| elements; order matters, and itertools.product generates it (with repeat for powers).
  • A partition splits a set into non-empty, disjoint blocks that cover it; the number of partitions of an n-element set is a Bell number.

Next: Relations, which are simply subsets of Cartesian products.