¿Cómo obtener todos los subconjuntos de un conjunto? (set de poder)

Dado un conjunto

{0, 1, 2, 3} 

¿Qué es una buena manera de producir los subconjuntos:

 [set(), {0}, {1}, {2}, {3}, {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}, {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}, {0, 1, 2, 3}] 

La página de itertools Python tiene exactamente una receta de conjunto de powerset para esto:

 def powerset(iterable): "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) 

Salida:

 >>> list(powerset("abcd")) [(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')] 

Si no te gusta esa tupla vacía al principio, puedes cambiar la instrucción de range(1, len(s)+1) a range(1, len(s)+1) para evitar una combinación de 0 longitud.

Aquí hay más código para un powerset. Esto está escrito desde cero:

 >>> def powerset(s): ... x = len(s) ... for i in range(1 << x): ... print [s[j] for j in range(x) if (i & (1 << j))] ... >>> powerset([4,5,6]) [] [4] [5] [4, 5] [6] [4, 6] [5, 6] [4, 5, 6] 

El comentario de Mark Rushakoff se aplica aquí: “Si no te gusta esa tupla vacía al principio, en.” Simplemente puede cambiar la instrucción de rango a rango (1, len (s) +1) para evitar una combinación de longitud 0 “, excepto en mi caso, cambia for i in range(1 << x) a for i in range(1, 1 << x) .


Volviendo a estos años más tarde, ahora lo escribiría así:

 def powerset(s): x = len(s) masks = [1 << i for i in range(x)] for i in range(1 << x): yield [ss for mask, ss in zip(masks, s) if i & mask] 

Y luego el código de prueba se vería así, diga:

 print(list(powerset([4, 5, 6]))) 

Usar yield significa que no necesita calcular todos los resultados en una sola pieza de memoria. Se supone que la precalculación de las máscaras fuera del bucle principal es una optimización que vale la pena.

Si estás buscando una respuesta rápida, solo busqué “power set de python” en google y encontré esto: Python Power Set Generator

Aquí hay una copia y pegar del código en esa página:

 def powerset(seq): """ Returns all the subsets of this set. This is a generator. """ if len(seq) <= 1: yield seq yield [] else: for item in powerset(seq[1:]): yield [seq[0]]+item yield item 

Esto se puede utilizar de esta manera:

  l = [1, 2, 3, 4] r = [x for x in powerset(l)] 

Ahora r es una lista de todos los elementos que deseaba, y puede ordenarse e imprimirse:

 r.sort() print r [[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]] 
 def powerset(lst): return reduce(lambda result, x: result + [subset + [x] for subset in result], lst, [[]]) 

Hay un refinamiento de powerset:

 def powerset(seq): """ Returns all the subsets of this set. This is a generator. """ if len(seq) <= 0: yield [] else: for item in powerset(seq[1:]): yield [seq[0]]+item yield item 
 def get_power_set(s): power_set=[[]] for elem in s: # iterate over the sub sets so far for sub_set in power_set: # add a new subset consisting of the subset at hand added elem power_set=power_set+[list(sub_set)+[elem]] return power_set 

Por ejemplo:

 get_power_set([1,2,3]) 

rendimiento

 [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 

Solo quería proporcionar la solución más comprensible, la versión de anti-code-golf.

 from itertools import combinations l = ["x", "y", "z", ] def powerset(items): combo = [] for r in range(len(items) + 1): #use a list to coerce a actual list from the combinations generator combo.append(list(combinations(items,r))) return combo l_powerset = powerset(l) for i, item in enumerate(l_powerset): print "All sets of length ", i print item 

Los resultados

Todos los conjuntos de longitud 0.

[()]

Todos los conjuntos de longitud 1.

[('x',), ('y',), ('z',)]

Todos los conjuntos de longitud 2.

[('x', 'y'), ('x', 'z'), ('y', 'z')]

Todos los conjuntos de longitud 3.

[('x', 'y', 'z')]

Para más información, consulte la documentación de itertools , también la entrada de wikipedia sobre los conjuntos de energía.

He encontrado el siguiente algoritmo muy claro y simple:

 def get_powerset(some_list): """Returns all subsets of size 0 - len(some_list) for some_list""" if len(some_list) == 0: return [[]] subsets = [] first_element = some_list[0] remaining_list = some_list[1:] # Strategy: get all the subsets of remaining_list. For each # of those subsets, a full subset list will contain both # the original subset as well as a version of the subset # that contains first_element for partial_subset in get_all_subsets(remaining_list): subsets.append(partial_subset) subsets.append(partial_subset[:] + [first_element]) return subsets 

Otra forma en que uno puede generar el conjunto de poderes es generando todos los números binarios que tienen n bits. Como potencia establecida, la cantidad de números con n dígitos es 2 ^ n . El principio de este algoritmo es que un elemento podría estar presente o no en un subconjunto, ya que un dígito binario podría ser uno o cero, pero no ambos.

 def power_set(items): N = len(items) # enumerate the 2 ** N possible combinations for i in range(2 ** N): combo = [] for j in range(N): # test bit jth of integer i if (i >> j) % 2 == 1: combo.append(items[j]) yield combo 

Encontré ambos algoritmos cuando estaba tomando MITx: 6.00.2x Introducción al pensamiento computacional y la ciencia de datos, y considero que es uno de los algoritmos más fáciles de entender que he visto.

¡Solo un rápido repaso de energía!

El conjunto de potencia de un conjunto X, es simplemente el conjunto de todos los subconjuntos de X, incluido el conjunto vacío

Ejemplo conjunto X = (a, b, c)

Conjunto de energía = {{a, b, c}, {a, b}, {a, c}, {b, c}, {a}, {b}, {c}, {}}

Aquí hay otra forma de encontrar el conjunto de poder:

 def power_set(input): # returns a list of all subsets of the list a if (len(input) == 0): return [[]] else: main_subset = [ ] for small_subset in power_set(input[1:]): main_subset += [small_subset] main_subset += [[input[0]] + small_subset] return main_subset print(power_set([0,1,2,3])) 

crédito completo a la fuente

TL; DR (ir directamente a Simplificación)

Sé que previamente he agregado una respuesta, pero realmente me gusta mi nueva implementación. Estoy tomando un conjunto como entrada, pero en realidad podría ser cualquier iterable, y estoy devolviendo un conjunto de conjuntos que es el conjunto de potencias de la entrada. Me gusta este enfoque porque está más alineado con la definición matemática del conjunto de poder ( conjunto de todos los subconjuntos ).

 def power_set(A): """A is an iterable (list, tuple, set, str, etc) returns a set which is the power set of A.""" length = len(A) l = [a for a in A] ps = set() for i in range(2 ** length): selector = f'{i:0{length}b}' subset = {l[j] for j, bit in enumerate(selector) if bit == '1'} ps.add(frozenset(subset)) return ps 

Si desea exactamente la salida que publicó en su respuesta, use esto:

 >>> [set(s) for s in power_set({1, 2, 3, 4})] [{3, 4}, {2}, {1, 4}, {2, 3, 4}, {2, 3}, {1, 2, 4}, {1, 2}, {1, 2, 3}, {3}, {2, 4}, {1}, {1, 2, 3, 4}, set(), {1, 3}, {1, 3, 4}, {4}] 

Explicación

Se sabe que el número de elementos del conjunto de potencias es 2 ** len(A) , por lo que se puede ver claramente en el bucle for .

Necesito convertir la entrada (idealmente un conjunto) en una lista porque, por un conjunto, es una estructura de datos de elementos desordenados únicos, y el orden será crucial para generar los subconjuntos.

selector es clave en este algoritmo. Tenga en cuenta que el selector tiene la misma longitud que el conjunto de entrada, y para hacer esto posible está utilizando una cadena de caracteres con relleno. Básicamente, esto me permite seleccionar los elementos que se agregarán a cada subconjunto durante cada iteración. Digamos que el conjunto de entrada tiene 3 elementos {0, 1, 2} , por lo que el selector tomará valores entre 0 y 7 (inclusive), que en binario son:

 000 # 0 001 # 1 010 # 2 011 # 3 100 # 4 101 # 5 110 # 6 111 # 7 

Por lo tanto, cada bit podría servir como un indicador si un elemento del conjunto original debe agregarse o no. Mire los números binarios, y piense en cada número como un elemento del super conjunto en el que 1 significa que se debe agregar un elemento en el índice j , y 0 significa que no se debe agregar este elemento.

Estoy utilizando una comprensión de conjuntos para generar un subconjunto en cada iteración, y convierto este subconjunto en un conjunto de datos de forma que pueda agregarlo a ps (conjunto de potencias). De lo contrario, no podré agregarlo porque un conjunto en Python consta solo de objetos inmutables.

Simplificación

Puede simplificar el código usando algunas comprensiones de Python, de modo que puede deshacerse de los de los bucles. También puede usar zip para evitar usar el índice j y el código terminará de la siguiente manera:

 def power_set(A): length = len(A) return { frozenset({e for e, b in zip(A, f'{i:{length}b}') if b == '1'}) for i in range(2 ** length) } 

Eso es. Lo que me gusta de este algoritmo es que es más claro y más intuitivo que otros, ya que parece bastante mágico confiar en sus itertools aunque funciona como se espera.

Esto es salvaje porque ninguna de estas respuestas en realidad proporciona el retorno de un conjunto de Python real. Aquí hay una implementación desordenada que le dará un conjunto de poderes que en realidad es un set Python.

 test_set = set(['yo', 'whatup', 'money']) def powerset( base_set ): """ modified from pydoc's itertools recipe shown above""" from itertools import chain, combinations base_list = list( base_set ) combo_list = [ combinations(base_list, r) for r in range(len(base_set)+1) ] powerset = set([]) for ll in combo_list: list_of_frozensets = list( map( frozenset, map( list, ll ) ) ) set_of_frozensets = set( list_of_frozensets ) powerset = powerset.union( set_of_frozensets ) return powerset print powerset( test_set ) # >>> set([ frozenset(['money','whatup']), frozenset(['money','whatup','yo']), # frozenset(['whatup']), frozenset(['whatup','yo']), frozenset(['yo']), # frozenset(['money','yo']), frozenset(['money']), frozenset([]) ]) 

Aunque me encantaría ver una mejor implementación.

Aquí está mi implementación rápida utilizando combinaciones pero utilizando solo elementos integrados.

 def powerSet(array): length = str(len(array)) formatter = '{:0' + length + 'b}' combinations = [] for i in xrange(2**int(length)): combinations.append(formatter.format(i)) sets = set() currentSet = [] for combo in combinations: for i,val in enumerate(combo): if val=='1': currentSet.append(array[i]) sets.add(tuple(sorted(currentSet))) currentSet = [] return sets 

Una forma simple sería aprovechar la representación interna de enteros bajo la aritmética del complemento de 2.

La representación binaria de enteros es como {000, 001, 010, 011, 100, 101, 110, 111} para números que van de 0 a 7. Para un valor de contador de enteros, considerando 1 como inclusión del elemento correspondiente en la colección y ‘0’ Como exclusión podemos generar subconjuntos basados ​​en la secuencia de conteo. Los números deben generarse de 0 a pow(2,n) -1 donde n es la longitud de la matriz, es decir, el número de bits en representación binaria.

Una simple función de generador de subconjuntos basada en ella se puede escribir como se muestra a continuación. Básicamente se basa

 def subsets(array): if not array: return else: length = len(array) for max_int in range(0x1 << length): subset = [] for i in range(length): if max_int & (0x1 << i): subset.append(array[i]) yield subset 

y luego puede ser usado como

 def get_subsets(array): powerset = [] for i in subsets(array): powerser.append(i) return powerset 

Pruebas

Agregando lo siguiente en el archivo local

 if __name__ == '__main__': sample = ['b', 'd', 'f'] for i in range(len(sample)): print "Subsets for " , sample[i:], " are ", get_subsets(sample[i:]) 

da siguiente salida

 Subsets for ['b', 'd', 'f'] are [[], ['b'], ['d'], ['b', 'd'], ['f'], ['b', 'f'], ['d', 'f'], ['b', 'd', 'f']] Subsets for ['d', 'f'] are [[], ['d'], ['f'], ['d', 'f']] Subsets for ['f'] are [[], ['f']]