Fun Problem: How to Programmatically List All Subsets of a Set

趣题：如何编程列出一个集合的所有子集 苏剑林 · 2016-03-04 · Machine Learning Python set

Fun problem: how to enumerate all subsets of a set programmatically

I recently ran into a task where I needed to implement a function that, given a set, lists all of its subsets. Interested readers might want to think about how to do this themselves before reading on.

While searching for references, I came across a rather elegant trick. more

This elegant trick makes use of binary numbers, and the inspiration is as follows: a set with $n$ elements has $2^n$ subsets, and it just so happens that there are also $2^n$ binary numbers with $n$ digits. So all we need to do is iterate over the first $2^n$ integers, convert each to binary, and then read off its digits one by one — whenever we hit a 1, we pick out the corresponding element from the original set. Implemented in Python, the code is remarkably concise:

import numpy as np

n = 5
s = np.array(range(n))
for i in range(2**n):
    e = list(bin(i))[2:]
    e = np.array(e) == '1'
    print s[n-len(e):][e]

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 world we're used to, the world of other number bases turns out to be pretty fascinating too!