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?
This question is related to
python
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.
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))
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
$ 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)]
>>>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']]
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
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
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.
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])
>>>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']]
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
$ 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)]
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))
Source: Stackoverflow.com