python - ¿Cuál es una buena manera de combinar a través de un conjunto?

set powerset

Question

Dado un conjunto

{a,b,c,d}

¿Cuál es una buena manera de producir

{a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,bcd,abcd}

?

Answer 1

Aquí está mi implementación rápida utilizando combinaciones pero usando solo complementos.

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

Answer 2

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 te gusta esa tupla vacía al principio, adelante", puedes simplemente cambiar la declaración de rango a rango (1, len (s) +1) para evitar una combinación de 0 de longitud ", excepto en mi caso cambias for i in range(1 << x) a 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í, por ejemplo:

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

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

Answer 3

Esto es salvaje porque ninguna de estas respuestas realmente proporciona el retorno de un conjunto de Python real. Aquí hay una implementación desordenada que dará un conjunto de poder 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.

Answer 4

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

Answer 5

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 poder 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 ciencia de datos, y considero que es uno de los algoritmos más fáciles de entender que he visto.

Answer 6

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

Answer 7

Si está buscando una respuesta rápida, busqué "power set de Python" en google y se me ocurrió esto: Python Power Set Generator

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 se puede ordenar e imprimir:

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

Answer 8

Solo quería ofrecer la solución más comprensible, la versión anti código 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 obtener más información, consulte los documentos de itertools , también la entrada de wikipedia en los conjuntos de poder.

Answer 9

"""
    from https://docs.python.org/3.6/library/itertools.html
    uses the module itertools
    chaining together the two functions combinations() and chain() is faster
    than iterating and generator functions in Python

    Author: joltE
    Date: 3/15/2017
"""
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    from itertools import chain, combinations 
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


def AllCombo(items):
    return [list(i) for i in powerset(items)]

Banco de pruebas

print(AllCombo([1, 3, 5, 7]))
print([list(i) for i in powerset([1, 3, 5, 7])])

powerset () actúa como una función de generador, pero es más eficiente debido al uso exclusivo de las funciones integradas de iterador de cadena () y combinaciones (). powerset () genera tuplas, esto se puede convertir en listas, como se hizo en AllCombo con la función list (). Ambas sentencias de impresión en el banco de pruebas emiten los mismos datos.

Answer 10

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

Answer 11

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