趣题：如何编程列出一个集合的所有子集

原文链接 | 2016-03-04 | 苏剑林

最近在一个编程中，需要实现一个功能，就是给定集合，如何列出它的所有子集。有兴趣的读者不妨自己想想怎么做？

在找资料的时候，发现了一个很奇妙的方法。

这个奇妙的方法就是利用二进制，灵感源于：\(n\)个元素的集合的所有子集有\(2^n\)个，而\(n\)位数的二进制数刚好也有\(2^n\)个。因此，只需要遍历前\(2^n\)个数，然后转为二进制，接着逐位读取，遇到1则挑选出原来集合对应的元素。如果用python实现，那么代码是非常简洁的：

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]

结果是

[]

[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]

除了我们习惯的10进制，其他进制的世界也相当奇妙呀！

---

---