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

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

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


转载到请包括本文地址:http://spaces.ac.cn/archives/3641/

如果您觉得本文还不错,欢迎点击下面的按钮对博主进行打赏。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!