在Python中生成所有k元素的子集

Question

我有一组数值，想要创建一个包含所有两个元素的子集的列表。

比如，源集合 ([1,2,3]) 有以下两个元素的子集：

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

有没有办法在Python中做到这一点呢？

Answer 1

为了提供另一种观点，我寻找了一种方法来遍历大小为2的所有子集，也就是从{1.....N}中选出两个数字，所以我测试了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))来遍历，因为这样会创建一个列表（而且比直接使用生成器要慢很多）。

Answer 2

这是集合 {1, 2, 3}（或者其他任何集合）的一个子集，里面包含了所有的两个元素的集合。

可以查看 Python的 itertools 文档，在里面搜索“powerset”这个词，可以找到这个问题的一般解答。

Answer 3

看起来你想用itertools.combinations这个工具：

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

如果你想要集合，你需要明确地转换它们。如果你不介意用可迭代的对象而不是列表，并且你在用Python 3的话，可以使用map：

>>> s = set((1, 2, 3))
>>> map(set, itertools.combinations(s, 2))
<map object at 0x10cdc26d8>

如果你想一次性查看所有结果，可以把map的输出传给list。在Python 2中，map的输出会自动变成列表。

>>> list(map(set, itertools.combinations(s, 2)))
[{1, 2}, {1, 3}, {2, 3}]

不过，如果你知道自己需要一个列表，使用列表推导式会稍微好一些（感谢Jacob Bowyer）：

>>> [set(i) for i in itertools.combinations(s, 2)]
[{1, 2}, {1, 3}, {2, 3}]

在Python中生成所有k元素的子集

4 个回答

撰写回答