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

Question

dado un conjunto

{a,b,c,d} 

lo que es una buena manera de producir

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

?

Answer 1

El pitón itertools page tiene exactamente una receta para este powerset:

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 que la tupla vacía al principio, sólo puede cambiar el range declaración a range(1, len(s)+1) para evitar una combinación de 0 longitudes.

Answer 2

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

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

de Mark Rushakoff se aplica aquí: "Si no te gusta que tupla vacía al principio, en" sólo puede cambiar el estado de gama en la gama (1, len . (s) 1) para evitar una combinación de longitud 0", excepto en caso de que cambie mi for i in range(1 << x) a for i in range(1, 1 << x)

---

volver a este años más tarde, yo ahora escribo de esta manera:

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í, dicen:

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

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

Answer 3

Si usted está buscando una respuesta rápida, acabo buscado "conjunto potencia pitón" en Google y se le ocurrió esto: Python Power Set Generator

Aquí está un copiar y pegar desde el código en la 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 puede ser usado como esto:

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

Ahora r es una lista de todos los elementos que quería, y pueden ser ordenados e impresos:

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 4

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

Answer 5

Sólo quería dar la solución más comprensible, la versión anticó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 más see the itertools docs, también la entrada de Wikipedia sobre power sets

Answer 6

Este es salvaje porque ninguno de estas respuestas realmente proporcionan 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 Python set.

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

Me encantaría ver una mejor implementación, sin embargo.

Answer 7

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 8

Aquí está mi aplicación rápida utilización de combinaciones, pero el uso de muebles empotrados solamente.

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 9

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 10

He encontrado el siguiente algoritmo muy clara 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 manera se puede generar el powerset es mediante la generación de todos 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 

me encontré con los dos algoritmos cuando estaba tomando MITX: Introducción a 6.00.2x pensamiento computacional y Ciencia de datos, y considero que es uno de los algoritmos más fáciles de entender que he visto.

Answer 11

""" 
    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 a que solo utilizando los itertools incorporados en la cadena de funciones() 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.