如何找到集合的所有子集，有n个元素?

I am writing a program in Python, and I realized that a problem I need to solve requires me, given a set S with n elements (|S|=n), to test a function on all possible subsets of a certain order m (i.e. with m number of elements). To use the answer to produce a partial solution, and then try again with the next order m=m+1, until m=n.

我正在用Python编写一个程序，我意识到我需要解决的一个问题需要我，给定一个有n个元素的集合S (|S|=n)，在所有可能的、具有m阶的子集(即m个元素)上测试一个函数。要使用这个答案生成一个部分解，然后再用下一阶m=m+1，直到m=n。

I am on my way to write a solution of the form:

我正在写一个表格的解决方案:

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

But knowing Python I expected a solution to be already there.

但是了解Python之后，我希望解决方案已经存在。

What is the best way to accomplish this?

实现这个目标的最好方法是什么?

5 个解决方案

#1

104

itertools.combinations is your friend if you have Python 2.6 or greater. Otherwise, check the link for an implementation of an equivalent function.

如果你有Python 2.6或更高版本，那么组合就是你的朋友。否则，请检查链接，以获得等效函数的实现。

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

S: The set for which you want to find subsets
m: The number of elements in the subset

S:要查找子集的集合m:子集中的元素个数

#2

Using the canonical function to get the powerset from the the itertools recipe page:

使用规范函数从itertools菜谱页面获取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))

Used like:

使用:

>>> 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 to sets if you want so you can use union, intersection, etc...:

映射到设置，如果你想这样你可以使用联合，交叉，等等…

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

#3

Here's a one-liner that gives you all subsets of the integers [0..n], not just the subsets of a given length:

这里有一个一行程序，它给出了整数的所有子集[0..n]，不只是给定长度的子集:

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

so e.g.

所以如。

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

#4

Here's some pseudocode - you can cut same recursive calls by storing the values for each call as you go and before recursive call checking if the call value is already present.

这里有一些伪代码——您可以通过在每次调用时存储值来减少相同的递归调用，并在递归调用检查之前检查调用值是否已经存在。

The following algorithm will have all the subsets excluding the empty set.

下面的算法将包含除空集之外的所有子集。

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;
    }
}

So, for example if s = "123" then output is:

例如，如果s = "123"则输出为:

#5

Without using itertools:

出现不使用itertools:

In Python 3 you can use yield from to add a subset generator method to buit-in set class:

在Python 3中，您可以使用yield to向buitin - 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()

For example below snippet works as expected:

例如，下面的代码片段按预期工作:

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

#1

104