How can I find all the subsets of a set, with exactly n elements?

Pietro_Speroni_46634 0
Viewed 133531

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.

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.

What is the best way to accomplish this?

python
10 Answers

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

recursive_447430

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

$ python -c "import itertools; a=[2,3,5,7,11]; print sum([list(itertools.combinations(a, i)) for i in range(len(a)+1)], [])" [(), (2,), (3,), (5,), (7,), (11,), (2, 3), (2, 5), (2, 7), (2, 11), (3, 5), (3, 7), (3, 11), (5, 7), (5, 11), (7, 11), (2, 3, 5), (2, 3, 7), (2, 3, 11), (2, 5, 7), (2, 5, 11), (2, 7, 11), (3, 5, 7), (3, 5, 11), (3, 7, 11), (5, 7, 11), (2, 3, 5, 7), (2, 3, 5, 11), (2, 3, 7, 11), (2, 5, 7, 11), (3, 5, 7, 11), (2, 3, 5, 7, 11)]

user_1562850 
>>>Set = ["A", "B","C","D"]
>>>n = 2
>>>Subsets=[[i for i,s in zip(Set, status) if int(s)  ] for status in [(format(bit,'b').zfill(len(Set))) for bit in range(2**len(Set))] if sum(map(int,status)) == n]
>>>Subsets
[['C', 'D'], ['B', 'D'], ['B', 'C'], ['A', 'D'], ['A', 'C'], ['A', 'B']]
user_118104700

Another solution using recursion:

def subsets(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    output = [[]]
    
    for num in nums:
        output += [curr + [num] for curr in output]
    
    return output

Starting from empty subset in output list. At each step we take a new integer into consideration and generates new subsets from the existing ones.

user_80115440

Here is an implementation using simple recursion from first principles. Base case: if there are no elements then return the empty set. Recursive case: choose an element and return all subsets of the other elements with and without the chosen element added.

def _all_subsets(s):
    seq = list(s)
    if not seq:
        yield set([])
    else:
        choice = set([seq[0]])
        others = seq[1:]
        for without_choice in _all_subsets(others):
            yield without_choice
            yield choice | without_choice

def all_subsets(iterable):
    s = set(iterable)
    for x in _all_subsets(s):
        yield x
user_1009810
Related