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

python

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?

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

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

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

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

Related

Recent Posts