什麼是通過一套組合的好方法？

Question

給定一組

{a,b,c,d} 

什麼是生產

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

的好辦法？

Answer 1

Python的itertools page正好有此一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)) 

輸出：

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

如果你不喜歡一開始是空的元組，你可以改變的range聲明到range(1, len(s)+1)以避免0長度的組合。

Answer 2

以下是powerset的更多代碼。這是從頭寫起：

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

馬克Rushakoff的評論這裏是適用的：「如果你不喜歡一開始是空的元組，對」你可以改變的範圍內聲明的範圍（1，LEN （S）+1），以避免一個長度爲0的組合」，除了在我的情況下更改for i in range(1 << x)到for i in range(1, 1 << x)

---

後來回到這幾年，我現在會寫這樣的：

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] 

然後測試代碼是這樣的，說：

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

使用yield意味着你不需要計算一整塊內存中的所有結果。預先計算主環路外的掩模被認爲是一種有價值的優化。

Answer 3

如果你正在尋找一個快速的答案，我只是搜查谷歌「巨蟒發電機組」以及與此想出了：Python Power Set Generator

下面是在頁面的代碼複製粘貼：

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 

這可以像這樣使用：

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

現在r爲所有你想要的元素列表，並且可以進行排序並打印：

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

我只是想提供最易於理解的解決方案，反碼高爾夫版本。

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 

---

結果

所有套長度的0

[()]

所有套長度的1

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

所有套長度的2

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

所有套長度3

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

的更多see the itertools docs，也power sets

Answer 6

的維基百科條目這是野生的，因爲沒有這些答案實際上提供了實際Python集的返回。這是一個混亂的實現，它將給出一個實際上是Python set的powerset。

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

雖然我很想看到更好的實現。

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 

例如：

get_power_set([1,2,3]) 

產量

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

Answer 8

這裏是我快速實現利用組合，但只使用內置插件。

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

有冪的改進：

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

我發現下面的算法非常簡單明瞭：

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 

另一種方法可以產生冪是通過生成所有具有n位的二進制數字。作爲一個功率設置n數字的數量是2^n。該算法的原理是元素可以存在或不存在於一個子集中，因爲二進制數字可以是一個或零，但不能同時存在。

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 

我發現，當我正在MITX兩種算法：6.00.2x介紹計算思維和數據科學，我認爲這是最簡單的算法之一瞭解我所看到的。

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

測試臺

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

冪（）的作用就像一個發電機的功能，但是更有效，因爲僅使用內置函數鏈（）以及它們的組合和itertools至（）。 powerset（）輸出元組，這可以轉換爲列表，就像在AllCombo中使用list（）函數一樣。測試平臺中的兩個打印語句都輸出相同的數據。