27 组合数学-子集合问题
目录
DFS或BFS解法
二项组合树解法
位运算解法
DFS或BFS解法
这个问题很简单，对于给定的集合，输出所有的子集合。对于这个问题，我们不用学习组合数学也知道这是2的n次方种子集合，特殊的有空集和平凡子集（也就是本身）。
以三个元素的集合为例子，我们可以把所有子集合化成一张图
上图中，N代表空的意思。也就是对于集合的每个元素，我们选择要这个元素还是不要这个元素。很明显，这是一个树状结构。对于树状结构，我们有两种算法，DFS与BFS。如果我们只用一个路径变量，很难存储每个结点从根部到自己的完整路径，所以采用节点本身存储自身到根部的路径的策略。Null是不能删除的，因为通过NULL凑数，就可以通过节点本身的路径长度判断节点自身所处的树层级，方便取子节点或结束寻找子节点过程。
思路找到了，代码写起来就非常容易了，以下是DFS算法的python代码：
def from_path(path): result = [] for e in path: if e is not None: result.append(e) return result# all subsets of setdef subsets(input): # DFS用的栈 stack = [[None]] # 路径 # 所有子集合 n = len(input) all_subsets = [] while len(stack) > 0: node = stack.pop() level = len(node) if level == n + 1: all_subsets.append(from_path(node)) else: # add children stack.append(node + [None]) stack.append(node + [input[level - 1]]) return all_subsetsif __name__ == '__main__': print(subsets([1, 2, 3]))输出结果：
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
二项组合树解法
前文已经介绍过，链接如下：
23 二项组合树_你的指尖有改变世界的力量-CSDN博客
但是代码有所不同，因为这里不能用剪枝策略。
def combinations(input): # 队列元素是集合加上索引的元组 queue = [([], 0)] result = [] while len(queue) > 0: e = queue.pop(0) result.append(e[0]) # 计算children subarray = input[e[1]:] for i, child in enumerate(subarray): x = (e[0] + [child], e[1] + i + 1) queue.append(x) return resultif __name__ == '__main__': print(combinations(['A', 'B', 'C']))测试结果：
[[], ['A'], ['B'], ['C'], ['A', 'B'], ['A', 'C'], ['B', 'C'], ['A', 'B', 'C']]位运算解法
我们考虑到每一个元素在不在子集合中，可以组成一个二进制的一位。所以N个元素的子集合就可以用二进制数字表示。如此可以避免频繁出栈入栈，不仅代码性能更高，而且更加简短清晰。
def from_mask(input, mask): result = [] for i, e in enumerate(input): if (1 << i) & mask != 0: result.append(e) return result# all subsets of setdef subsets(input): # DFS用的栈 # 路径 # 所有子集合 n = len(input) all_subsets = [from_mask(input, mask) for mask in range(0, 1 << n)] return all_subsetsif __name__ == '__main__': print(subsets([1, 2, 3]))输出结果
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]