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

10 minutos de lectura

¿Como obtener todos los subconjuntos de un conjunto set de
Patricio

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}]

  • ¿Cuáles son las aplicaciones de un powerset?

    – X10D

    19 de noviembre de 2020 a las 23:49

  • @ X10D muchos. Por ejemplo: erudito.google.com/…

    – Alejandro Huat

    20 de enero de 2021 a las 13:07

  • La mayoría de los resultados no parecen estar relacionados con un conjunto de potencia. ¿Puede enumerar algunas aplicaciones?

    – X10D

    21 de enero de 2021 a las 10:50

  • @ X10D Para los algoritmos de descubrimiento causal basados ​​​​en restricciones, uno necesita probar la independencia condicional condicionando todos los subconjuntos posibles de las variables involucradas, también me encontré con la necesidad del conjunto de potencia al calcular la serie de Fourier para funciones booleanas. Esta es obviamente la punta del iceberg

    – Nazaral

    28 de marzo de 2021 a las 16:21

  • @ X10D Preguntar cuáles son las aplicaciones de un conjunto de potencia es un poco como preguntar cuáles son las aplicaciones de los subconjuntos. Es un concepto matemático fundamental. Para qué usarlo depende de ti. Lo he usado para probar varias combinaciones de cosas. Suponga que su conjunto contiene acciones y desea probar todos los subconjuntos de acciones posibles. Iterar sobre el conjunto de potencia se siente natural.

    – DustByte

    18 de febrero a las 11:11

1646753113 243 ¿Como obtener todos los subconjuntos de un conjunto set de
marca rushakoff

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.

  • Esta es la respuesta más rápida que pude encontrar, comparando algunas otras soluciones en esta página con esta usando el módulo timeit de Python. Sin embargo, en ciertos casos, si necesita modificar la salida resultante (p. ej., unir las letras para formar cadenas), escribir una receta personalizada utilizando generadores y generar la salida que desea (p. ej., sumar dos cadenas) puede ser mucho más rápido.

    – César Bautista

    23 de febrero de 2018 a las 7:48

  • por que es s = list(iterable) ¿necesario?

    – Jack Stevens

    14 de marzo de 2018 a las 12:23

  • @JackStevens porque los iterables no se pueden rebobinar y no es necesario que tengan __len__ implementado; probar powerset((n for n in range(3))) sin el ajuste de la lista.

    – hurgando

    21 de marzo de 2018 a las 22:14

  • para cadenas grandes, ¡esto consumiría mucha memoria!

    – Editor novato

    24 de agosto de 2018 a las 4:39

  • @AlexandreHuat: los rangos son secuencias perezosas, no iteradores. powerset(range(3)) funcionaría bien Incluso sin s = list(iterable).

    – user2357112 apoya a Mónica

    27 de marzo de 2020 a las 9:10

¿Como obtener todos los subconjuntos de un conjunto set de
hughdbrown

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.

  • Esta es una respuesta creativa. Sin embargo, lo medí usando timeit para compararlo con Mark Rushakoff y noté que era significativamente más lento. Para generar el conjunto de potencia de 16 elementos 100 veces, mis medidas fueron 0,55 frente a 15,6.

    – César Bautista

    23 de febrero de 2018 a las 7:40


  • ¿Cómo manejas los duplicados?

    – llamaro25

    7 de marzo de 2021 a las 4:25

  • Cualquier problema de duplicados en python se puede resolver usando set().

    – Inocencia

    17 de mayo de 2021 a las 6:36

  • @CeasarBautista no puede comparar una función de usuario con una función integrada. Las funciones integradas siempre se optimizan siempre que sea posible

    – lxg95

    24 de julio de 2021 a las 14:27

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

  • En caso de una matriz vacía como entrada, el código anterior devolvería [[][]]para arreglar eso, simplemente separe los casos para verificar la longitud if len(seq) == 0: yield [] elif len(seq) == 1: yield seq yield []

    – Ayush

    18/10/2017 a las 18:32


  • Como referencia, medí esto (con la edición de Ayush) usando timeit y lo comparé con la receta de powerset en la respuesta de Mark Rushakoff. En mi máquina, para generar el powerset de 16 elementos 100 veces, este algoritmo tardó 1,36 segundos, mientras que el de Rushakoff tardó 0,55.

    – César Bautista

    23 de febrero de 2018 a las 7:44

  • ¿Cuál será la complejidad del tiempo para esto?

    – CodeQuestor

    16 de agosto de 2019 a las 7:24

  • @CodeQuestor Evalué la complejidad del tiempo de la sección de copiar y pegar. Para mí, se siente como O(n^2). El ciclo for contribuye con 1 n, la llamada recursiva contribuye con n-1. Entonces, en total se convierte en O (n ^ 2). Junto a estos, si consideramos un bucle exterior que llama a powerset(l), otro n se multiplica con el resultado anterior, convirtiéndolo en O(n^3). Soy principiante y estudiante en esto. Así que por favor corrígeme si mi perspectiva es incorrecta. Mantenerse a salvo.

    – MANEESH MOHAN

    9 de junio de 2021 a las 14:37


def powerset(lst):
    return reduce(lambda result, x: result + [subset + [x] for subset in result],
                  lst, [[]])

¿Como obtener todos los subconjuntos de un conjunto set de
miguelvargasf

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.

1646753116 996 ¿Como obtener todos los subconjuntos de un conjunto set de
Jinguo Yao

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.

  • Esta es básicamente la misma idea que en esta respuesta anterior stackoverflow.com/a/1482320/4434666

    – tomasz

    21 de agosto de 2021 a las 1:36

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad