Bitmask as a Set

The Idea

Give each item a lane. Then one integer describes a whole subset: lane i is 1 when item i is in.

Counting from 0 to 2^n - 1 therefore enumerates every subset, in order, with no recursion. Union is |, intersection is &, membership is mask >> i & 1.

Real-World Example

Travelling-salesman and scheduling solvers keep "which cities have I already visited?" as one 20-bit integer. It is the dictionary key for memoisation — comparing and hashing a set of 20 items collapses to comparing two machine words.

The Code

items = ["a", "b", "c"]

for mask in range(1 << len(items)):   # 0 .. 7
    picked = [items[i] for i in range(len(items)) if mask >> i & 1]
    print(mask, format(mask, "03b"), picked)

# 0 000 []
# 1 001 ['a']
# 2 010 ['b']
# 3 011 ['a', 'b']
# ...
# 7 111 ['a', 'b', 'c']

items = ["a", "b", "c"]
mask = 5

picked = [items[i] for i in range(3) if ___]
print(picked)   # want ['a', 'c']