jaki jest dobry sposób na połączenie zestawu?

Question

Biorąc pod uwagę zestaw

{a,b,c,d} 

co jest dobrym sposobem, aby produkować

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

?

Answer 1

Python itertools page ma dokładnie do powerset przepis na to:

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

wyjściowa:

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

Jeśli nie lubisz tego pustego krotki na początku, można po prostu zmienić range oświadczenie do range(1, len(s)+1), aby uniknąć kombinacji 0-długości.

Answer 2

Oto więcej kodu dla zestawu. To jest napisany od podstaw: Komentarz

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

Mark Rushakoff jest zastosowanie tutaj: „Jeśli nie lubią tego pustego krotki na początku, na” można po prostu zmienić oświadczenie range się w przedziale (1, len . (s) +1), aby uniknąć kombinacji 0 długości”, chyba że w moim przypadku zmiany for i in range(1 << x) do for i in range(1, 1 << x)

---

powrót do tego lata później, będę teraz napisać to tak:

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] 

A potem kod testowy będzie wyglądać tak, powiedzieć:

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

Korzystanie yield oznacza, że ​​nie trzeba obliczyć wszystkie wyniki w jednym kawałku pamięci. Wstępna kalkulacja masek poza główną pętlą jest uważana za opłacalną optymalizację.

Answer 3

Jeżeli szukasz szybkiej odpowiedzi, po prostu szukał „python zestaw zasilania” na google i podszedł z tym: Python Power Set Generator

Oto copy-paste z kodu w tej stronie:

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 

ten może być stosowany tak:

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

teraz r jest lista wszystkich elementów Państwo chcieli, i może być sortowana i drukowana:

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

Chciałem tylko, aby zapewnić najbardziej zrozumiałe rozwiązanie, anty wersję kodu golfowe.

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 

---

Wyniki

Wszystkie zestawy o długości 0

[()]

Wszystkie zestawy o długości 1

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

Wszystkie zestawy o długości 2

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

Wszystkie zestawy o długości 3

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

Dla bardziej see the itertools docs również wpis wikipedia na power sets

Answer 6

To jest dziki, ponieważ żaden tych odpowiedzi faktycznie zapewnia powrót rzeczywistego zestawu Pythona. Oto nieuporządkowana implementacja, która da zestaw, który faktycznie jest Pythonem 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([]) ]) 

Chciałbym jednak zobaczyć lepszą implementację.

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 

Na przykład:

get_power_set([1,2,3]) 

wydajność

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

Answer 8

Tu jest moja szybka realizacja z wykorzystaniem kombinacji, ale tylko przy użyciu Zabudowy.

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

Jest udoskonalenie 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

znalazłem następujący algorytm bardzo jasne i proste:

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 

Innym sposobem można wygenerować PowerSet jest poprzez generowanie wszystkich liczby binarne o bitach n. Jako zestaw mocy ilość cyfr z cyframi n wynosi 2^n. Zasada działania tego algorytmu polega na tym, że element może występować w podzbiorze, ponieważ cyfra binarna może być równa lub zerowa, ale nie może mieć obu.

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 

znalazłem oba algorytmy kiedy brał mITX: Introduction to Computational 6.00.2x myślenia i danych naukowych, i uważam, że jest to jeden z najprostszych algorytmów zrozumieć widziałem.

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

hamowni

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

PowerSet() zachowuje się jak funkcja generatora, ale jest bardziej efektywne ze względu na jedynie za pomocą itertools łańcuchu w funkcji() i połączenia(). powerset() wyprowadza krotki, można to przekonwertować na listy, tak jak zrobiono to w AllCombo z funkcją list(). Obie instrukcje drukowania w tabeli testowej wyświetlają te same dane.