Generating subsets¶

In this post, we will discuss the problem of generating all subsets of a given set of elements. A subset is a collection of elements that are selected from a set. The table below shows all subsets of the set {1, 2, 3}:

Subsets of {1, 2, 3}
{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}

For a set of $n$ elements, there are $2^n$ subsets. The problem of generating all subsets of a set of elements is a common problem in computer science and has applications in various fields, such as combinatorial optimization, cryptography, and data analysis.

We use a small helper to print a subset in set notation.

def show(subset):
    """Format a subset as {a1, a2}, or ∅ for the empty set."""
    return "{" + ", ".join(map(str, subset)) + "}" if subset else "∅"

1. Binary representation¶

Each subset of $\{a_1, \ldots, a_n\}$ corresponds to a bit string $b_1 b_2 \ldots b_n$ of length $n$ , where $b_i = 1$ means $a_i$ is in the subset and $b_i = 0$ means it is not. To generate all subsets, we generate the binary numbers from 0 to $2^n - 1$ and translate each one into a subset.

def subsets_binary(elements):
    n = len(elements)
    result = []
    for k in range(2 ** n):
        bits = format(k, f"0{n}b")  # k as an n-bit string, e.g. 5 -> '101'
        subset = [elements[i] for i in range(n) if bits[i] == "1"]
        result.append((bits, subset))
    return result


for bits, subset in subsets_binary(["a1", "a2", "a3"]):
    print(bits, show(subset))

000 ∅
001 {a3}
010 {a2}
011 {a2, a3}
100 {a1}
101 {a1, a3}
110 {a1, a2}
111 {a1, a2, a3}

This reproduces the table in the slides: bit $b_1$ (the leftmost) stands for $a_1$ .

Squashed order¶

In squashed order, every subset that involves $a_j$ comes after all the subsets of $\{a_1, \ldots, a_{j-1}\}$ . The order above is not squashed: $\{a_3\}$ comes before $\{a_1\}$ . To get squashed order, we read the bits from right to left instead, so that the least significant bit stands for $a_1$ . Bit $i$ of $k$ is (k >> i) & 1.

def subsets_squashed(elements):
    n = len(elements)
    result = []
    for k in range(2 ** n):
        subset = [elements[i] for i in range(n) if (k >> i) & 1]
        result.append(subset)
    return result


for subset in subsets_squashed(["a1", "a2", "a3"]):
    print(show(subset))

∅
{a1}
{a2}
{a1, a2}
{a3}
{a1, a3}
{a2, a3}
{a1, a2, a3}

2. Bottom-up¶

The bottom-up algorithm is a decrease-by-one algorithm. It relies on one observation: every subset of $\{a_1, \ldots, a_n\}$ either contains $a_n$ or it does not, so

\text{Subsets}(n) = \text{Subsets}(n-1) \;\cup\; \{\, S \cup \{a_n\} \mid S \in \text{Subsets}(n-1) \,\}

(1)

The algorithm builds the $2^n$ subsets incrementally, adding one element at a time. Start with the only subset of the empty set, $\emptyset$ . Then, for each new element $a_i$ , keep all the subsets generated so far (those not containing $a_i$ ) and append a copy of each of them with $a_i$ added (those containing $a_i$ ). Each step doubles the list.

def subsets_bottom_up(elements):
    subsets = [[]]  # n = 0: only the empty set
    for a in elements:
        subsets = subsets + [s + [a] for s in subsets]
    return subsets

Printing the list after each step gives the table from the slides:

elements = ["a1", "a2", "a3"]
for n in range(len(elements) + 1):
    print(n, "  ".join(show(s) for s in subsets_bottom_up(elements[:n])))

0 ∅
1 ∅  {a1}
2 ∅  {a1}  {a2}  {a1, a2}
3 ∅  {a1}  {a2}  {a1, a2}  {a3}  {a1, a3}  {a2, a3}  {a1, a2, a3}

The same idea can be written as a recursion that follows the recurrence directly: solve the problem for the first $n-1$ elements, then add $a_n$ to a copy of each of those subsets.

def subsets_recursive(elements):
    if not elements:
        return [[]]
    smaller = subsets_recursive(elements[:-1])  # all subsets of {a1, ..., a(n-1)}
    a_n = elements[-1]
    return smaller + [s + [a_n] for s in smaller]


print([show(s) for s in subsets_recursive([1, 2, 3])])

['∅', '{1}', '{2}', '{1, 2}', '{3}', '{1, 3}', '{2, 3}', '{1, 2, 3}']

Both versions produce the subsets in squashed order, the same order as the binary method with the bits read from right to left:

letters = ["a", "b", "c", "d", "e"]
assert subsets_bottom_up(letters) == subsets_recursive(letters) == subsets_squashed(letters)
print("All three agree on", len(subsets_bottom_up(letters)), "subsets")

All three agree on 32 subsets

3. The binary reflected Gray code algorithm¶

The binary reflected Gray code (BRGC) is a minimal-change algorithm: it generates the $2^n$ bit strings so that successive strings differ in exactly one bit. In terms of subsets, each subset is obtained from the previous one by adding or removing a single element.

The list for $n$ bits is built from the list for $n-1$ bits. The second half of the list is the first half reflected, that is, in reverse order:

BRGC(n):
    if n = 1, make list L of the two bit strings 0 and 1
    else
        generate recursively list L1 of bit strings of length n-1
        copy list L1 in reverse order to get list L2
        add 0 in front of each bit string in list L1
        add 1 in front of each bit string in list L2
        append L2 to L1 to get list L
    return L

We can implement the algorithm using recursion as follows:

def gray_code(n):
    if n == 1:
        return ["0", "1"]
    else:
        L1 = gray_code(n - 1)
        L2 = L1[::-1]
        L1 = ["0" + x for x in L1]
        L2 = ["1" + x for x in L2]
        return L1 + L2


for n in range(2, 5):
    print(f"n = {n}:", " ".join(gray_code(n)))

n = 2: 00 01 11 10
n = 3: 000 001 011 010 110 111 101 100
n = 4: 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

The function gray_code(n) generates the Gray code for $n$ bits. The base case is when $n = 1$ , in which case the function returns the list ['0', '1']. Otherwise, the function generates the Gray code for $n-1$ bits and copies the list in reverse order. It then adds '0' as a prefix to each bit string in the original list and '1' as a prefix to each bit string in the reversed list. Finally, it appends the reversed list to the original list and returns the result.

We can avoid the recursion and the extra copies of the list by growing a single list in place. The following iterative implementation appends the reflected strings with a '1' prefix, then adds the '0' prefix to the first half:

def gray_code_iterative(n):
    if n <= 0:
        raise ValueError("n must be greater than 0")

    gray_code_list = ["0", "1"]
    for i in range(2, n + 1):
        # reflect: append the existing strings in reverse order, prefixed with '1'
        for j in range(len(gray_code_list) - 1, -1, -1):
            gray_code_list.append("1" + gray_code_list[j])

        # prefix the first half (the original strings) with '0'
        for j in range(len(gray_code_list) // 2):
            gray_code_list[j] = "0" + gray_code_list[j]

    return gray_code_list


assert all(gray_code_iterative(n) == gray_code(n) for n in range(1, 11))
print(" ".join(gray_code_iterative(3)))

000 001 011 010 110 111 101 100

We can check the minimal-change property, and translate the bit strings into subsets:

def differs_in_one_bit(s, t):
    return sum(x != y for x, y in zip(s, t)) == 1


codes = gray_code(4)
assert all(differs_in_one_bit(codes[i], codes[i + 1]) for i in range(len(codes) - 1))

elements = ["a1", "a2", "a3"]
for bits in gray_code(len(elements)):
    print(bits, show([elements[i] for i in range(len(elements)) if bits[i] == "1"]))

000 ∅
001 {a3}
011 {a2, a3}
010 {a2}
110 {a1, a2}
111 {a1, a2, a3}
101 {a1, a3}
100 {a1}

Application: the knapsack problem¶

The exhaustive-search solution to the knapsack problem examines every subset of items, computes its total weight and value, and keeps the most valuable subset that fits in the knapsack. If the subsets are generated independently, computing the totals of each one takes linear time.

With the Gray code order, consecutive subsets differ by one item, so the totals of the new subset are obtained from those of the previous one in constant time: add the item’s weight and value if it was just added, subtract them if it was just removed.

To find which bit changes at step $k$ without comparing strings, we use a property of the BRGC: the bit that flips at step $k$ (counting from the right, starting at 0) is the number of trailing zeros in the binary representation of $k$ . For example, from step 3 to step 4 (010 → 110), $4 = 100_2$ has two trailing zeros, so bit 2, the leftmost one, flips.

def knapsack_gray(weights, values, capacity):
    n = len(weights)
    chosen = [0] * n  # current subset as a bit string, b1 first; start with ∅
    total_weight = total_value = 0
    best_value, best_items = 0, []

    for k in range(1, 2 ** n):
        trailing_zeros = (k & -k).bit_length() - 1
        i = n - 1 - trailing_zeros  # index of the bit that flips, counted from the left
        chosen[i] ^= 1

        sign = 1 if chosen[i] else -1  # item i was added (+) or removed (-)
        total_weight += sign * weights[i]
        total_value += sign * values[i]

        if total_weight <= capacity and total_value > best_value:
            best_value = total_value
            best_items = [j + 1 for j in range(n) if chosen[j]]

    return best_value, best_items

We use the instance from the brute-force chapter: four items and a knapsack of capacity 10.

Item	Weight	Value
1	7	42
2	3	12
3	4	25
4	5	40

best_value, best_items = knapsack_gray(weights=[7, 3, 4, 5], values=[42, 12, 25, 40], capacity=10)
print("Best value:", best_value, "with items", show(best_items))

Best value: 65 with items {3, 4}