How to find all subsets of a set with exactly n elements?

Question

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

I am going to write a solution to the form:

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

But knowing Python, I was expecting a solution to already exist.

What is the best way to do this?

Answer 1

itertools.combinations is your friend if you have Python 2.6 or higher. Otherwise, check the link to implement the equivalent function.

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

Answer 2

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

 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 as:

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

sets if you want you to be able to 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]) 

Answer 3

Here is a single line that gives you all subsets of integers [0..n], and not just subsets of a given length:

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

eg,

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

Answer 4

Here is some pseudo-code - you can cut out the same recursive calls, storing the values ​​for each call in the process, and before the recursive call checks if the call value is already present.

The following algorithm will have all 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 the output:

 1 2 3 12 13 23 123 

Answer 5

Without using itertools :

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

 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, the 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