我如何找到一個集合的所有子集，正好有n個元素？

Question

我正在用Python編寫一個程序，並且我意識到我需要解決的一個問題需要我，給定一組S和n元素（| S | = n），以測試某個特定順序的所有可能子集上的函數（即具有m元素的數量）。要使用答案產生部分解，然後用下一個階m = m + 1再次嘗試，直到m = n。

我對我的方式來寫形式的解決方案：

def findsubsets(S, m): 
    subsets = set([]) 
    ... 
    return subsets 

但我們知道的Python我期望的解決方案，已經到了。

完成此操作的最佳方法是什麼？

Answer 1

itertools.combinations是你的朋友，如果你有Python 2.6或更高版本。否則，請檢查鏈接以獲取等效函數的實現。

import itertools 
def findsubsets(S,m): 
    return set(itertools.combinations(S, m)) 

Answer 2

這裏是一個一行，讓您的整數[0到n]，給定長度的不只是子集的所有子集：

from itertools import combinations, chain 
allsubsets = lambda n: list(chain(*[combinations(range(n), ni) for ni in range(n+1)])) 

所以如

>> allsubsets(3) 
[(), (0,), (1,), (2,), (0, 1), (0, 2), (1, 2), (0, 1, 2)] 

Answer 3

下面是一些僞代碼 - 你可以通過存儲的數值爲每個呼叫，當您去和遞歸調用檢查，如果調用值已經存在前斷絕同遞歸調用。

以下算法將具有排除空集的所有子集。

list * subsets(string s, list * v) { 

    if(s.length() == 1) { 
     list.add(s);  
     return v; 
    } 
    else 
    { 
     list * temp = subsets(s[1 to length-1], v); 
     int length = temp->size(); 

     for(int i=0;i<length;i++) { 
      temp.add(s[0]+temp[i]); 
     } 

     list.add(s[0]); 
     return temp; 
    } 
} 

因此，舉例來說，如果S = 「123」 則輸出爲：

1 
2 
3 
12 
13 
23 
123 

Answer 4

使用規範的功能，從the itertools recipe頁面獲得powerset：

from itertools import chain, combinations 

def powerset(iterable): 
    """ 
    powerset([1,2,3]) -->() (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3) 
    """ 
    xs = list(iterable) 
    # note we return an iterator rather than a list 
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1)) 

一樣使用：

>>> list(powerset("abc")) 
[(), ('a',), ('b',), ('c',), ('a', 'b'), ('a', 'c'), ('b', 'c'), ('a', 'b', 'c')] 

>>> list(powerset(set([1,2,3]))) 
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] 

地圖設置，如果你想使您可以使用集，交集，等...：

>>> map(set, powerset(set([1,2,3]))) 
[set([]), set([1]), set([2]), set([3]), set([1, 2]), set([1, 3]), set([2, 3]), set([1, 2, 3])] 

>>> reduce(lambda x,y: x.union(y), map(set, powerset(set([1,2,3])))) 
set([1, 2, 3]) 

Answer 5

不使用itertools：

在Python 3，你可以使用yield from增加一個子集生成方法到BUIT-在set類：

class SetWithSubset(set): 
    def subsets(self): 
     s1 = [] 
     s2 = list(self) 

     def recfunc(i=0):    
      if i == len(s2): 
       yield frozenset(s1) 
      else:     
       yield from recfunc(i + 1) 
       s1.append(s2[ i ]) 
       yield from recfunc(i + 1) 
       s1.pop() 

     yield from recfunc() 

例如下面的代碼片段按預期工作：

x = SetWithSubset({1,2,3,5,6}) 
{2,3} in x.subsets()   # True 
set() in x.subsets()   # True 
x in x.subsets()    # True 
x|{7} in x.subsets()   # False 
set([5,3]) in x.subsets()  # True - better alternative: set([5,3]) < x 
len(x.subsets())    # 32