How to use recursion to get a subset by splitting the set into the first and remaining parts (python)
I want to write a function using recursion to get a subset of the set and print like this when we enter [1, 2, 3] as set:
[
[],
[1],
[2],
[3],
[1, 2],
[1, 3],
[2, 3],
[1, 2, 3]
]
My thinking breaks the set into two parts, the first and the second. Then use the first one to add each item to the rest.
Here is my code:
def subset(set):
if len(set) == 0:
return [set]
elif len(set) == 1:
return [set[0]]
else:
short = subset(set[1:])
alist=[]
for item in short:
blist=[set[0]]
blist.append(item)
alist.append(blist)
return alist
This does not work. How to fix it? (Allow only one parameter, set)
source to share
Assuming the items don't have duplicates.
def subset(l):
if not l:
return [[]]
rest = subset(l[1:])
return rest + [[l[0]] + s for s in rest]
The output is not quite in the order you need:
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
But we can try to sort the resulting list of subsets. Assuming the elements of the list are always integers, we can try:
sorted(subset([1, 2, 3]), key=lambda l : int('0' + ''.join(str(i) for i in l)))
And then we have the desired result:
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
source to share
I believe this should do the trick, although I should probably sleep, so let me know if it doesn't.
def rec(l, _s=None):
if _s is None:
_s = []
_s.append(tuple(l))
for i, null in enumerate(l):
sl = [v for j, v in enumerate(l) if i != j]
if len(sl) > 0:
rec(sl, _s)
_s = set(_s)
return _s
print rec([1,2,3,4])
Alternatively without recursive:
import itertools
def norec(l):
s = []
for i in range(len(l)):
s.extend(itertools.combinations(l, i+1))
return s
Finally, recursive with only one parameter. It's a little awkward.
def rec2(l):
new = [l]
for i, null in enumerate(l):
sub = [v for j, v in enumerate(l) if i != j]
new.extend(rec2(sub))
return set([tuple(x) for x in new])
source to share
I think creating a power circuit is a good exercise in recursion, but it's usually best to do things iteratively if possible; Python has no optimizations for recursion.
It is possible to use powerets with one layer using reduce
, but since Guido doesn't like it reduce
I'll make a slightly longer version. :)
>>> def powerset(seq):
... z = [[]]
... for x in seq:
... z += [y + [x] for y in z]
... return z
...
>>> ps = powerset(range(1, 5)); ps.sort(key=lambda i:(len(i), i)); ps
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4],
[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]
(I've manually wrapped the output to avoid scrolling).
source to share
I think the drayescat gave the correct answer. Check out the code below to see where your code went wrong versus it if you haven't figured it out already :-).
def subset(set):
if len(set) == 0:
return [set]
elif len(set) == 1: # actually we do not need it
#return [set[0]] # this is wrong
return [set] + [[]] #this is correct, although redundant
else:
short = subset(set[1:])
alist=[]
for item in short:
blist=[set[0]]
#blist.append(item) #item is a list, so do not append it to blist
blist += item #addition
alist.append(blist)
return short + alist # you have to add this "short" which is the return value of the last "subset" call
print(subset([1,2,3]))
#print(sorted(subset([1, 2, 3]), key=lambda l : int('0' + ''.join(str(i) for i in l))))
source to share