qual è un buon modo per combinare attraverso un set?

Question

dato un insieme

{a,b,c,d} 

che cosa è un buon modo per produrre

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

?

Answer 1

Il Python itertools page ha esattamente una ricetta powerset per questo:

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

uscita:

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

Se non ti piace che tupla vuota all'inizio, si può semplicemente cambiare il range dichiarazione a range(1, len(s)+1) per evitare una combinazione di lunghezza 0.

Answer 2

Ecco un altro codice per un gruppo di continuità. Questo è scritto da zero: commento

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

Marco Rushakoff è applicabile qui: "Se non come quella tupla vuota all'inizio, sul tema" si può semplicemente modificare l'istruzione gamma di gamma (1, len . (s) +1) al fine di evitare una combinazione 0-length", tranne che nel mio caso si cambia for i in range(1 << x) a for i in range(1, 1 << x)

---

tornare in questo anni più tardi, mi piacerebbe ora scrivo in questo modo:

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] 

E poi il codice di test sarebbe simile a questa, dicono:

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

Utilizzando yield significa che non è necessario calcolare tutti i risultati in un unico pezzo di memoria. Il calcolo preliminare delle maschere al di fuori del ciclo principale è considerato un'ottimizzazione utile.

Answer 3

Se siete alla ricerca di una risposta rapida, ho solo cercato "insieme potenza python" su google e arrivato fino a questo: Python Power Set Generator

Ecco un copia-incolla dal codice in quella pagina:

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 

questo può essere utilizzato in questo modo:

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

Ora r è un elenco di tutti gli elementi che volevi, e possono essere ordinati e stampati:

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

Volevo solo per fornire la soluzione più comprensibili, l'anti versione del codice-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 

---

I risultati

Tutti gli insiemi di lunghezza 0

[()]

Tutti gli insiemi di lunghezza 1

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

Tutti i set di lunghezza 2

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

Tutti i set di lunghezza 3

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

Per ulteriori see the itertools docs, anche la voce di Wikipedia su power sets

Answer 6

Questo è selvaggio perché nessuno di queste risposte forniscono in realtà il ritorno di un vero set Python. Ecco un'implementazione disordinata che darà un powerset che in realtà è 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([]) ]) 

Mi piacerebbe vedere un'implementazione migliore, però.

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 

Ad esempio:

get_power_set([1,2,3]) 

resa

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

Answer 8

Ecco la mia implementazione rapida utilizzando combinazioni, ma utilizzando solo built-in.

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

V'è un perfezionamento del 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

ho trovato il seguente algoritmo molto chiaro e semplice:

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 

altro modo si può generare il powerset è generando tutti numeri binari che hanno n bit. Come potenza impostata, la quantità di numero con cifre n è 2^n. Il principio di questo algoritmo è che un elemento potrebbe essere presente o meno in un sottoinsieme come una cifra binaria potrebbe essere uno o zero ma non entrambi.

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 

ho trovato entrambi gli algoritmi quando mi stava prendendo MITX: Introduzione 6.00.2x al pensiero computazionale e Science Data, e ritengo che è uno degli algoritmi più semplici per capire che ho 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 prova

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

powerset() agisce come una funzione generatore, ma è più efficiente a causa solo utilizzando i itertools incorporate catena funzioni() e combinazioni(). powerset() emette tuple, questo può essere convertito in liste, come è stato fatto in AllCombo con la funzione list(). Entrambe le istruzioni di stampa nel banco di prova producono gli stessi dati.