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

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

这个奇妙的方法就是利用二进制，灵感源于：$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进制，其他进制的世界也相当奇妙呀！

转载到请包括本文地址：https://kexue.fm/archives/3641

更详细的转载事宜请参考：《科学空间FAQ》

如果您还有什么疑惑或建议，欢迎在下方评论区继续讨论。

如果您觉得本文还不错，欢迎分享/打赏本文。打赏并非要从中获得收益，而是希望知道科学空间获得了多少读者的真心关注。当然，如果你无视它，也不会影响你的阅读。再次表示欢迎和感谢！

如果您需要引用本文，请参考：

苏剑林. (Mar. 04, 2016). 《趣题：如何编程列出一个集合的所有子集 》[Blog post]. Retrieved from https://kexue.fm/archives/3641

@online{kexuefm-3641,
        title={趣题：如何编程列出一个集合的所有子集},
        author={苏剑林},
        year={2016},
        month={Mar},
        url={\url{https://kexue.fm/archives/3641}},
}