Generar todos los subconjuntos de tamaño k (que contienen elementos k) en Python

Question

Tengo un conjunto de valores y me gustaría crear una lista de todos los subconjuntos que contienen 2 elementos.

Por ejemplo, una fuente establecer ([1,2,3]) tiene los siguientes subconjuntos de 2 elementos:

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

¿Hay una manera de hacer esto en Python?

Answer 1

parece que quiere itertools.combinations:

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

Si desea conjuntos que tendrá que convertir explícitamente.

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

Answer 2

Este es un subconjunto de la power set de {1, 2, 3} (o cualquier conjunto) que contiene todos los conjuntos de dos elementos.

Consulte el Python itertools documentation y busque el término "powerset" para obtener una respuesta general a este problema.

Answer 3

sólo para dar otro punto de vista, me puse a buscar una manera de recorrer todo el subconjunto de tamaño 2 de {1.....N}, por lo que poner itertools.combinations en la prueba:

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 

así que supongo que no siempre se debe convertir en general solución ... Si sabe de antemano el tamaño del subconjunto que desea, debería ser más eficiente iterar usando ciclos for.

También tenga en cuenta que no debe iterar sobre list(itertools.combinations(lst, 2)) ya que este movimiento crea la lista (y mucho más lento que usar el generador).