dado un conjunto

{0, 1, 2, 3}

¿Cómo puedo 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}]

el pitón itertools página tiene exactamente un powerset receta para esto:

from itertools import chain, combinations

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))

Producción:

>>> 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 le gusta esa tupla vacía al principio, simplemente puede cambiar la range declaración a range(1, len(s)+1) para evitar una combinación de longitud 0.

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 es aplicable aquí: “Si no le gusta esa tupla vacía al principio, en”. Puede cambiar la declaración de rango a rango (1, len (s) + 1) para evitar una combinación de longitud 0 “, excepto en mi caso cambias for i in range(1 << x) para for i in range(1, 1 << x).

Volviendo a esto años después, 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í, digamos:

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

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

Si está buscando una respuesta rápida, acabo de buscar “conjunto de potencia de python” en Google y se me ocurrió esto: Generador de conjuntos de potencia de Python

Aquí hay un copiar 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 usar así:

 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, [[]])

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_powerset(remaining_list):
        subsets.append(partial_subset)
        subsets.append(partial_subset[:] + [first_element])

    return subsets

Otra forma en que uno puede generar el powerset es generando todos los números binarios que tienen n pedacitos Como una potencia establece la cantidad de número con n dígitos es 2 ^ n. El principio de este algoritmo es que un elemento puede estar presente o no en un subconjunto, ya que un dígito binario puede 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.

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

TL; DR (ir directamente a Simplificación)

Sé que previamente agregué una respuesta, pero realmente me gusta mi nueva implementación. Estoy tomando un conjunto como entrada, pero en realidad podría ser iterable, y estoy devolviendo un conjunto de conjuntos que es el conjunto de potencia de la entrada. Me gusta este enfoque porque está más alineado con la definición matemática de set 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 el resultado 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 potencia es 2 ** len(A)por lo que se podía ver claramente en el for lazo.

Necesito convertir la entrada (idealmente un conjunto) en una lista porque 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 selector tiene la misma longitud que el conjunto de entrada y, para que esto sea posible, utiliza una cadena f 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 selector tomará valores entre 0 y 7 (ambos inclusive), que en binario son:

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

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

Estoy usando una comprensión de conjunto para generar un subconjunto en cada iteración, y convierto este subconjunto en un frozenset para que pueda agregarlo ps (set de poder). De lo contrario, no podré agregarlo porque un conjunto en Python consiste solo en objetos inmutables.

Simplificación

Puede simplificar el código utilizando algunas comprensiones de python, de modo que pueda deshacerse de los bucles for. También puedes usar zip para evitar el uso j index 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 todo. Lo que me gusta de este algoritmo es que es más claro e intuitivo que otros porque parece bastante mágico confiar en él. itertools a pesar de que funciona como se esperaba.