今天這一題是求冪集。小學數學都忘得差不多了… 冪集是什麼？ 冪集（power set）是一個集合的所有子集。比如[1, 2, 3]的冪集就是： [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 不過這道題有一個額外的要求： 在求冪集時要以“ ...
今天這一題是求冪集。小學數學都忘得差不多了… 冪集是什麼？
冪集（power set）是一個集合的所有子集。比如[1, 2, 3]的冪集就是：
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
不過這道題有一個額外的要求：
在求冪集時要以“深度優先搜索”（depth-first search）的形式進行。也就是說，對於集合的每個元素，都有“取”和“舍”兩種選擇；在深度優先時，我們優先選擇“舍”。仍以[1, 2, 3]為例，在這種情況下，它的冪集應該是：
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
現在給定一個列表，如何以深度優先遍歷的方法找出它的冪集？
這道題有兩種思路。第一種，是採用回溯法。用白話說，就是在每一個分叉路口，偏執的選擇一條道走到黑，此時再返回至上一個路口選擇另外一條道繼續… 這個過程相當於下麵這個二叉樹：
用遞歸實現非常簡單：用對應輸入集合列表的另一個列表res保存當前這條路上每個元素是取還是舍，然後繼續往前走直到列表末尾，最後輸出這條路上所有是“取”的元素。實現時為簡單起見使用了嵌套函數。
def powerset(nums): powerset = [] res = [0] * len(nums) def visit(i): if i == len(nums): powerset.append([num for j, num in enumerate(nums) if res[j] == 1]) # 輸出這條路上所有是“取”的元素 else: res[i] = 0 visit(i+1) # 先“舍”，繼續往前走 res[i] = 1 visit(i+1) # 再“取”，繼續往前走 visit(0) return powerset
另外一種思路是觀察：
[1, 2, 3] -> [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
冪集是不是相當於[1, 2, 3]按照[0, 0, 0], [0, 0, 1], … [1, 1, 1]選擇出來的？而[0, 0, 0], [0, 0, 1], … [1, 1, 1]既可以看成0-7的二進位表達，也可以看作是3個(0, 1)的笛卡爾積。
實現要點：
1. 對一個集合按照selector進行選擇：
用itertools的compress方法。
2. 將十進位數轉換為前面補0的固定長度的二進位數：
用format函數。
3. 求多個集合的笛卡爾積：
用itertools的product方法。
借用某個最優解法如下：
from itertools import product, compress def powerset(nums): return [list(compress(nums, pattern)) for pattern in product((0, 1), repeat=len(nums))]
其實，如果沒有深度優先的要求，求一個集合的冪集是非常簡單的，用itertools模塊的combinations方法就可以輕鬆做到：
from itertools import combinations def power(s): return [list(c) for i in range(len(s)+1) for c in combinations(s, i)]
解決一個問題的方法多多，最重要是善於觀察和總結，對嗎？
