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)

+3

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]]
```

```
+3

source

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

```
+2

source

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

+2

source

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

```
+1

source

All Articles