Генерация всех подмножеств размера k (содержащих k элементов) в Python

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)]

Если вы хотите наборы, вам придется конвертировать их явно.Если вы не возражаете против итерации вместо списка и используете 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}]

Однако, если вы знаете, что вам нужен список, понимание списка немного лучше (h / t Джейкоб Бауэр ):

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

Answer 2

Это подмножество набора мощности из {1, 2, 3} (или любого другого набора), содержащего все двухэлементные наборы.

См. Документацию по Python itertools и найдите термин "powerset" для общего ответа на эту проблему.

Answer 3

Просто, чтобы дать другую перспективу, я искал способ итерировать все подмножества размера 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)) так как этот шаг создает список (и намного медленнее, чем использование самого генератора).