Encuentre en python combinaciones de conjuntos mutuamente exclusivos de los elementos de una lista

En un proyecto en el que estoy trabajando, he implementado aproximadamente el 80% de lo que quiero que haga mi progtwig y estoy muy contento con los resultados.

En el 20% restante me enfrento a un problema que me desconcierta un poco sobre cómo resolverlo. Aquí está:

He creado una lista de listas que contienen varios números (longitud arbitraria) Por ejemplo:

listElement[0] = [1, 2, 3] listElement[1] = [3, 6, 8] listElement[2] = [4, 9] listElement[4] = [6, 11] listElement[n] = [x, y, z...] 

donde n podría alcanzar hasta 40,000 o menos.

Suponiendo que cada elemento de la lista es un conjunto de números (en el sentido matemático), lo que me gustaría hacer es derivar todas las combinaciones de conjuntos mutuamente excluyentes; es decir, como el conjunto de potencias de los elementos de la lista anterior, pero con todos los elementos de conjuntos no disociados excluidos.

Entonces, para continuar el ejemplo con n = 4, me gustaría crear una lista que tenga las siguientes combinaciones:

 newlistElement[0] = [1, 2, 3] newlistElement[1] = [3, 6, 8] newlistElement[2] = [4, 9] newlistElement[4] = [6, 11] newlistElement[5] = [[1, 2, 3], [4, 9]] newlistElement[6] = [[1, 2, 3], [6, 11]] newlistElement[7] = [[1, 2, 3], [4, 9], [6, 11]] newlistElement[8] = [[3, 6, 8], [4, 9]] newlistElement[9] = [[4, 9], [6, 11] 

Un caso no válido, por ejemplo, sería combinación [[1, 2, 3], [3, 6, 8]] porque 3 es común en dos elementos. ¿Hay alguna manera elegante de hacer esto? Estaría extremadamente agradecido por cualquier comentario.

También debo especificar que no me gustaría hacer la función de conjunto de poder, porque la lista inicial podría tener un número bastante grande de elementos (como dije que podría subir a 40000), y tomar el conjunto de poder con tantos elementos nunca terminaría .

El método utilizado en el progtwig a continuación es similar a un par de respuestas anteriores al excluir conjuntos no disjuntos y, por lo tanto, generalmente no prueba todas las combinaciones. Se diferencia de las respuestas anteriores al excluir con avidez todos los conjuntos que puede, tan pronto como sea posible. Esto permite que se ejecute varias veces más rápido que la solución de NPE. Aquí hay una comparación de tiempo de los dos métodos, utilizando datos de entrada con 200, 400, … 1000 conjuntos de tamaño 6 que tienen elementos en el rango de 0 a 20:

 Set size = 6, Number max = 20 NPE method 0.042s Sizes: [200, 1534, 67] 0.281s Sizes: [400, 6257, 618] 0.890s Sizes: [600, 13908, 2043] 2.097s Sizes: [800, 24589, 4620] 4.387s Sizes: [1000, 39035, 9689] Set size = 6, Number max = 20 jwpat7 method 0.041s Sizes: [200, 1534, 67] 0.077s Sizes: [400, 6257, 618] 0.167s Sizes: [600, 13908, 2043] 0.330s Sizes: [800, 24589, 4620] 0.590s Sizes: [1000, 39035, 9689] 

En los datos anteriores, la columna izquierda muestra el tiempo de ejecución en segundos. Las listas de números muestran cuántas uniones simples, dobles o triples ocurrieron. Las constantes en el progtwig especifican tamaños y características de conjuntos de datos.

 #!/usr/bin/python from random import sample, seed import time nsets, ndelta, ncount, setsize = 200, 200, 5, 6 topnum, ranSeed, shoSets, shoUnion = 20, 1234, 0, 0 seed(ranSeed) print 'Set size = {:3d}, Number max = {:3d}'.format(setsize, topnum) for casenumber in range(ncount): t0 = time.time() sets, sizes, ssum = [], [0]*nsets, [0]*(nsets+1); for i in range(nsets): sets.append(set(sample(xrange(topnum), setsize))) if shoSets: print 'sets = {}, setSize = {}, top# = {}, seed = {}'.format( nsets, setsize, topnum, ranSeed) print 'Sets:' for s in sets: print s # Method by jwpat7 def accrue(u, bset, csets): for i, c in enumerate(csets): y = u + [c] yield y boc = bset|c ts = [s for s in csets[i+1:] if boc.isdisjoint(s)] for v in accrue (y, boc, ts): yield v # Method by NPE def comb(input, lst = [], lset = set()): if lst: yield lst for i, el in enumerate(input): if lset.isdisjoint(el): for out in comb(input[i+1:], lst + [el], lset | set(el)): yield out # Uncomment one of the following 2 lines to select method #for u in comb (sets): for u in accrue ([], set(), sets): sizes[len(u)-1] += 1 if shoUnion: print u t1 = time.time() for t in range(nsets-1, -1, -1): ssum[t] = sizes[t] + ssum[t+1] print '{:7.3f}s Sizes:'.format(t1-t0), [s for (s,t) in zip(sizes, ssum) if t>0] nsets += ndelta 

Edición: En la (u, bset, csets) funciones, los argumentos (u, bset, csets) se usan de la siguiente manera:
• u = lista de conjuntos en la unión actual de conjuntos
• bset = “big set” = valor plano de u = elementos ya utilizados
• csets = candidato sets = lista de sets elegibles para ser incluidos
Tenga en cuenta que si la primera línea de accrue se sustituye por
def accrue(csets, u=[], bset=set()):
y la séptima línea por
for v in accrue (ts, y, boc):
(es decir, si los parámetros se reordenan y los valores predeterminados se dan para u y bset), la acumulación se puede invocar a través de [accrue(listofsets)] para producir su lista de uniones compatibles.

Con respecto a ValueError: zero length field name in format error de ValueError: zero length field name in format mencionado en un comentario como ocurre cuando se usa Python 2.6, intente lo siguiente.

 # change: print "Set size = {:3d}, Number max = {:3d}".format(setsize, topnum) # to: print "Set size = {0:3d}, Number max = {1:3d}".format(setsize, topnum) 

Es posible que se necesiten cambios similares (agregar números de campo apropiados) en otros formatos en el progtwig. Tenga en cuenta que la página Novedades de la versión 2.6 dice: “El soporte para el método str.format () ha sido portado a Python 2.6”. Si bien no dice si se requieren nombres de campo o números, no muestra ejemplos sin ellos. Por el contrario, de cualquier manera funciona en 2.7.3.

Yo usaría un generador:

 import itertools def comb(seq): for n in range(1, len(seq)): for c in itertools.combinations(seq, n): # all combinations of length n if len(set.union(*map(set, c))) == sum(len(s) for s in c): # pairwise disjoint? yield list(c) for c in comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]): print c 

Esto produce:

 [[1, 2, 3]] [[3, 6, 8]] [[4, 9]] [[6, 11]] [[1, 2, 3], [4, 9]] [[1, 2, 3], [6, 11]] [[3, 6, 8], [4, 9]] [[4, 9], [6, 11]] [[1, 2, 3], [4, 9], [6, 11]] 

Si necesita almacenar los resultados en una sola lista:

 print list(comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]])) 

El siguiente es un generador recursivo:

 def comb(input, lst = [], lset = set()): if lst: yield lst for i, el in enumerate(input): if lset.isdisjoint(el): for out in comb(input[i+1:], lst + [el], lset | set(el)): yield out for c in comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]): print c 

Es probable que esto sea mucho más eficiente que las otras soluciones en situaciones en las que muchos conjuntos tienen elementos comunes (por supuesto, en el peor de los casos, todavía tiene que iterar sobre los elementos 2**n del conjunto de energía).

utilizando itertools.combinations , set.intersection y for-else loop:

 from itertools import * lis=[[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]] def func(lis): for i in range(1,len(lis)+1): for x in combinations(lis,i): s=set(x[0]) for y in x[1:]: if len(s & set(y)) != 0: break else: s.update(y) else: yield x for item in func(lis): print item 

salida:

 ([1, 2, 3],) ([3, 6, 8],) ([4, 9],) ([6, 11],) ([1, 2, 3], [4, 9]) ([1, 2, 3], [6, 11]) ([3, 6, 8], [4, 9]) ([4, 9], [6, 11]) ([1, 2, 3], [4, 9], [6, 11]) 

Similar a la solución de NPE , pero sin recursión y devuelve una lista:

 def disjoint_combinations(seqs): disjoint = [] for seq in seqs: disjoint.extend([(each + [seq], items.union(seq)) for each, items in disjoint if items.isdisjoint(seq)]) disjoint.append(([seq], set(seq))) return [each for each, _ in disjoint] for each in disjoint_combinations([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]): print each 

Resultado:

 [[1, 2, 3]] [[3, 6, 8]] [[1, 2, 3], [4, 9]] [[3, 6, 8], [4, 9]] [[4, 9]] [[1, 2, 3], [6, 11]] [[1, 2, 3], [4, 9], [6, 11]] [[4, 9], [6, 11]] [[6, 11]] 

One-liner sin emplear el paquete itertools. Aquí están tus datos:

 lE={} lE[0]=[1, 2, 3] lE[1] = [3, 6, 8] lE[2] = [4, 9] lE[4] = [6, 11] 

Aquí está el de una sola línea:

 results=[(lE[v1],lE[v2]) for v1 in lE for v2 in lE if (set(lE[v1]).isdisjoint(set(lE[v2])) and v1>v2)]