TAOCP 2.2.3 Exercise 12

Let $S$ be a set of $n$ elements.

taocpmathematicsalgorithmsvolume-1math-medium

Section 2.2.3: Linked Allocation

Exercise 12. [M20] There are $2^n$ subsets of a set of $n$ elements, and these subsets are partially ordered by the set-inclusion relation. Give two interesting ways to arrange these subsets in topological order.

Verified: yes
Solve time: 48s

Solution

Let $S$ be a set of $n$ elements. The family of all subsets of $S$ contains $2^n$ elements and is partially ordered by inclusion. A topological order is any linear arrangement in which

$$ A \subset B \implies A \text{ precedes } B. $$

Two natural topological arrangements are as follows.

First, arrange the subsets by increasing cardinality. Thus all subsets of size $0$ come first, then all subsets of size $1$, then all subsets of size $2$, and so on, ending with the subsets of size $n$. Within each group of equal cardinality, the subsets may be arranged arbitrarily.

To verify that this is a topological order, suppose $A \subset B$. If $A=B$ there is nothing to prove. If $A\subset B$ properly, then

$$ |A|<|B|. $$

Hence every subset $A$ appears in an earlier cardinality class than $B$. Therefore $A$ precedes $B$, and the arrangement is topological.

A second arrangement is obtained by identifying each subset with its characteristic binary vector. If

$$ S={x_1,x_2,\ldots,x_n}, $$

associate with each subset $A$ the binary number

$$ (b_1b_2\cdots b_n)_2, $$

where

$$ b_i= \begin{cases} 1,&x_i\in A,\ 0,&x_i\notin A. \end{cases} $$

Arrange the subsets in increasing order of these binary numbers.

This is a topological order because $A\subset B$ implies that whenever $b_i=1$ for $A$, the corresponding digit for $B$ is also $1$. If $A\ne B$, there is at least one position where $A$ has digit $0$ and $B$ has digit $1$. Let $j$ be the leftmost such position. Then the binary representation of $A$ and $B$ agree in all earlier positions, while at position $j$ the digit of $A$ is $0$ and that of $B$ is $1$. Therefore the binary number corresponding to $A$ is smaller than that corresponding to $B$, so $A$ precedes $B$.

Thus two interesting topological orderings are:

  1. Order by increasing cardinality of the subsets.
  2. Order by increasing value of the characteristic binary number of each subset.

$$ \boxed{\text{Topological orders: (i) by cardinality, (ii) by characteristic binary number.}} $$