Chapter IV Set Packing

Branch-and-bound in Python

Python's frozenset and bit-twiddling get you a clean, fast-enough enumerator.

01

Encode each set as an integer — bit i is set if element i is in the set. Disjointness is a single AND check, which is what makes branch-and-bound feasible at any scale.
```
def encode(sets):
    elems = sorted({e for s in sets for e in s})
    idx = {e: i for i, e in enumerate(elems)}
    return [sum(1 << idx[e] for e in s) for s in sets]
```

Recursive search: at each step, either include the current set (if disjoint from the running union) or skip it. Track the best size found so far for pruning.

def pack(sets, i=0, used=0, picked=()):
    if i == len(sets):
        return picked
    best = pack(sets, i+1, used, picked)
    if sets[i] & used == 0:
        cand = pack(sets, i+1, used | sets[i], picked + (i,))
        if len(cand) > len(best):
            best = cand
    return best

Add a bound: if the remaining sets can't beat the current best even if all are picked, prune. Real solvers use LP relaxations for tighter bounds; this is the schoolbook version.

def pack_pruned(sets, i, used, picked, best):
    if len(picked) + (len(sets) - i) <= len(best):
        return best
    if i == len(sets):
        return picked if len(picked) > len(best) else best
    if sets[i] & used == 0:
        best = pack_pruned(sets, i+1, used | sets[i], picked + (i,), best)
    return pack_pruned(sets, i+1, used, picked, best)

04

Try it on a small instance. For families much beyond 30 sets, you want PuLP or OR-Tools wrapping a real MIP solver — but the recursion above is the algorithm those solvers are doing under the hood.
```
>>> sets = [{1,2}, {3,4}, {2,3}, {5}]
>>> bits = encode(sets)
>>> pack_pruned(bits, 0, 0, (), ())
(0, 1, 3)   # picks {1,2}, {3,4}, {5}
```

Grammar — Python

Python's strength here is that sets and integers stand in for each other naturally. Small sets compile cleanly to bit-tricks, and the syntax stays close to the math.

def f(x, y=0):: function definition. y=0 is a default parameter. Indentation marks the body.
{e for x in xs}: set comprehension. Add `if cond` for a filter. {e: f(e) for ...} gives a dict.
1 << i: left shift — produces an integer with only bit i set. Python ints are arbitrary precision.
a & b: bitwise AND. On large integers, Python treats them as bitsets.
(a, b, c): a tuple — immutable sequence. Often used as keys or running accumulators.
lambda x: expr: anonymous function, limited to one expression. For more, use def.
enumerate(xs): yields (i, x) pairs. Saves you from manual indexing.
>>>: the interactive REPL prompt — anything after it is a line you typed.

Encode the set {1, 2, 5} as the integer with bits 1, 2, and 5 turned on. Disjointness — "do these sets share any element?" — collapses to a single AND.

def encode(s):
    return sum(1 << i for i in s)

a = encode({1, 2, 5})    # 0b100110 = 38
b = encode({3, 4, 7})    # 0b10011000 = 152
disjoint = (a & b) == 0  # True — no shared bits

Python — official tutorial →