Recently, during a programming project, I needed to implement a feature to list all subsets of a given set. Interested readers might want to think about how to achieve this themselves.
While searching for references, 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 2^n possible values. Therefore, one only needs to iterate through the first 2^n numbers, convert them to binary, and then read them bit by bit, selecting the corresponding element from the original set whenever a "1" is encountered. If implemented in Python, the code is very 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 results are:
[] [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]
Beyond the decimal system we are accustomed to, the worlds of other bases are truly fascinating!
When reposting, please include the original address of this article: https://kexue.fm/archives/3641
For more detailed information regarding reposting, please refer to: Scientific Space FAQ