在Python中生成大小爲k（包含k個元素）的所有子集

Question

我有一組值並希望創建包含2個元素的所有子集的列表。

例如，源設置([1,2,3])有以下2種元素的子集：

set([1,2]), set([1,3]), set([2,3]) 

有沒有辦法在Python做到這一點？

Answer 1

好像你要itertools.combinations：

>>> list(itertools.combinations((1, 2, 3), 2)) 
[(1, 2), (1, 3), (2, 3)] 

如果你想套你必須給他們明確的轉化。

>>> s = set((1, 2, 3)) 
>>> map(set, itertools.combinations(s, 2)) 
[set([1, 2]), set([1, 3]), set([2, 3])] 

Answer 2

這是{1, 2, 3}（或任何集合）的power set的包含所有二元素集的子集。

查看Python itertools documentation並搜索術語「powerset」以獲得對此問題的一般答案。

Answer 3

只給另一個角度看，我找了一個方法來遍歷的{1.....N}尺寸2的所有子集，所以我把itertools.combinations到測試：

import itertools 
from time import time 


N = 7000 
lst = [i for i in xrange(N)] 

st = time() 
c1 = 0 
for x in itertools.combinations(lst, 2): 
    c1 += 1 
print "combinations: %f" % (time()-st) 

st = time() 
c2=0 
for x in xrange(N): 
    for y in xrange(x): 
     c2 += 1 
print "double loop: %f" % (time()-st) 
print "c1=%d,c2=%d" % (c1,c2) 

# prints: 
#combinations: 4.247000 
#double loop: 3.479000 
# c1=24496500,c2=24496500 

所以我想你不應該總是變成一般解決方案....如果您事先知道所需子集的大小，則使用for循環進行迭代應該更有效。

另請注意，由於此操作會創建列表（並且比使用生成器本身慢得多），因此您不應該重複執行list(itertools.combinations(lst, 2))。