By 苏剑林 | March 04, 2016
Recently, during a programming task, I needed to implement a function to list all subsets of a given set. Interested readers might want to think about how they would approach this themselves.
While searching for resources, I discovered a very ingenious method.
This ingenious method utilizes binary numbers. The inspiration comes from the fact that a set with $n$ elements has $2^n$ subsets, and an $n$-bit binary number also has exactly $2^n$ possible variations. Therefore, one only needs to iterate through the numbers from $0$ to $2^n - 1$, convert them to binary, and then read each bit; whenever a 1 is encountered, select the element from the original set corresponding to that position. If implemented in Python, the code is remarkably concise:
import numpy as np
s = np.array(range(5))
n = len(s)
for i in range(2**n):
b = bin(i)[2:].zfill(n)
print(s[[j == '1' for j in b]])
The result is:
[]
[4]
[3]
[3 4]
[2]
[2 4]
[2 3]
[2 3 4]
[1]
[1 4]
[1 3]
[1 3 4]
[1 2]
[1 2 4]
[1 2 3]
[1 2 3 4]
[0]
[0 4]
[0 3]
[0 3 4]
[0 2]
[0 2 4]
[0 2 3]
[0 2 3 4]
[0 1]
[0 1 4]
[0 1 3]
[0 1 3 4]
[0 1 2]
[0 1 2 4]
[0 1 2 3]
[0 1 2 3 4]
Besides the base-10 system we are accustomed to, the world of other bases is also quite wonderful!