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?
Answers:
Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.
Method 1
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
Method 2
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])
Method 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)]
Method 4
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))
Method 5
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:
1 2 3 12 13 23 123
Method 6
Without using itertools:
In Python 3 you can use yield from to add a subset generator method to 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 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
Method 7
$ 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)]
Method 8
>>>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']]
Method 9
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.
Method 10
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
All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0