У меня есть набор значений и хотел бы создать список всех подмножеств, содержащих 2 элемента.
Например, исходный набор ([1,2,3]) имеет следующие 2-элементные подмножества:
set([1,2]), set([1,3]), set([2,3])
Есть ли способ сделать это в python?
Сгенерировать все подмножества размера k (содержащие k элементов) в Python
Ответ 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])]
Ответ 2
Это подмножество power set {1, 2, 3} (или любого другого), содержащего все двухэлементные множества.
Смотрите Python itertools документацию и выполните поиск по термину "poweret" для общего ответа на эту проблему.
Ответ 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
Итак, я думаю, вы не всегда должны превращаться в общее решение.... Если вы заранее знаете размер подмножества, который вы хотите, он должен быть более эффективным для итерации с использованием для циклов.
Также обратите внимание, что вы не должны перебирать list(itertools.combinations(lst, 2)), так как это перемещение создает список (и намного медленнее, чем использование самого генератора).