Genera tutti i sottoinsiemi di dimensione k (contenenti k elementi) in Python

Question

Ho un set di valori e vorrei creare un elenco di tutti i sottoinsiemi contenenti 2 elementi.

Per esempio, una fonte impostare ([1,2,3]) presenta i seguenti sottoinsiemi 2-elemento:

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

C'è un senso fare questo in Python?

Answer 1

Sembra che si desidera itertools.combinations:

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

Se si vuole set dovrete convertirli in modo esplicito.

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

Answer 2

Questo è un sottoinsieme della power set di {1, 2, 3} (o qualunque set) contenente tutti i set di due elementi.

Vedere Python itertools documentation e cercare il termine "gruppo di accensione" per una risposta generale a questo problema.

Answer 3

solo per dare un'altra prospettiva, ho cercato un modo per scorrere tutte sottoinsieme del formato 2 di {1.....N}, così ho messo itertools.combinations in prova:

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 

quindi credo che non dovrebbe girare sempre nella generale soluzione .... Se conosci in anticipo la dimensione del sottoinsieme che desideri, dovrebbe essere più efficiente per iterare usando i cicli.

Si noti inoltre che non si deve eseguire iterazione su list(itertools.combinations(lst, 2)) poiché questa mossa crea l'elenco (e molto più lento dell'utilizzo del generatore stesso).