How can I find all the subsets of a set, with exactly n elements?
Using the canonical function to get the powerset from the the itertools recipe 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 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])
Here is one neat way with easy to understand algorithm.
import copy
nums = [2,3,4,5]
subsets = [[]]
for n in nums:
prev = copy.deepcopy(subsets)
[k.append(n) for k in subsets]
subsets.extend(prev)
print(subsets)
print(len(subsets))
# [[2, 3, 4, 5], [3, 4, 5], [2, 4, 5], [4, 5], [2, 3, 5], [3, 5], [2, 5], [5],
# [2, 3, 4], [3, 4], [2, 4], [4], [2, 3], [3], [2], []]
# 16 (2^len(nums))
Here's a function that gives you all subsets of the integers [0..n], not just the subsets of a given length:
from itertools import combinations, chain
def allsubsets(n):
return 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)]
itertools.combinations is your friend if you have Python 2.6 or greater. Otherwise, check the link for an implementation of an equivalent function.
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