Python recursive function to display all subsets of given set

Question

I have the following python function to print all subsets of a list of numbers:

def subs(l):
    if len(l) == 1:
        return [l]
    res = []
    for sub in subs(l[0:-1]):
        res.append(sub)
        res.append([l[-1]])
        res.append(sub+[l[-1]])
    return res

li = [2, 3, 5, 8]
print(subs(li))

This returns:

[[2], [8], [2, 8], [5], [8], [5, 8], [2, 5], [8], [2, 5, 8], [3], [8], [3, 8], [5], [8], [5, 8], [3, 5], [8], [3, 5, 8], [2, 3], [8], [2, 3, 8], [5], [8], [5, 8], [2, 3, 5], [8], [2, 3, 5, 8]]

Which is not the expected answer. It looks like python takes the list l into the function by reference. So when I append l[-1], it appends the last element of original list, not the smaller list sent into the recursive method. Is there any way to solve this?

This could possibly be solved using tuples but I'm wondering if there is a solution using lists.

Answer 1

def subs(l):
    if l == []:
        return [[]]

    x = subs(l[1:])

    return x + [[l[0]] + y for y in x]

Results:

>>> print (subs([1, 2, 3]))
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Answer 2

There is a convenient Python module to help:

import itertools
def subs(l):
    res = []
    for i in range(1, len(l) + 1):
        for combo in itertools.combinations(l, i):
            res.append(list(combo))
    return res

The results are:

>>> subs([1,2,3])
[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Answer 3

Actually there is no problem with Python call by reference as I originally thought. In that case l[-1] would be 8 in all recursive calls. But l[-1] is 3, 5, 8 respectively in the recursive calls. This modified function solves the issue:

def subs(l):
    if len(l) == 1:
        return [l]
    res = []
    subsets = subs(l[0:-1])
    res = res+subsets
    res.append([l[-1]])
    for sub in subsets:
        res.append(sub+[l[-1]])
    return res

returns:

[[2], [3], [2, 3], [5], [2, 5], [3, 5], [2, 3, 5], [8], [2, 8], [3, 8], [2, 3, 8], [5, 8], [2, 5, 8], [3, 5, 8], [2, 3, 5, 8]]

Answer 4

Improving on @Miguel Matos answer

def subsets(set_inp):
    if set_inp == []:
        return [[]]
    x = subsets(set_inp[1:])

    return sorted( x + [[set_inp[0]] + y for y in x])
print(subsets([1,2,3]))

Answer 5

using @Miguel Matos idea we can get these in lexicographical order by,

def foo(l, p = [], d = {}):
    if len(l)==0: 
        return [[]]
    
    x = foo(l[:-1])
    
    return x+ [[l[-1]] + y for y in x]

returns

[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1], [4], [4, 1], [4, 2], [4, 2, 1], [4, 3], [4, 3, 1], [4, 3, 2], [4, 3, 2, 1]]

Answer 6

You can avoid using comprehensions or for-loops by using lambda functions and map.

I consider this a proper 'functional' powerset function in Python:

def powerSet(input):


# at tree leaf, return leaf
if len(input)==0:
    return [[]];

# if not at a leaf, trim and recurse
# recursion is illustrated as follows:
# e.g. S = {1,2,3}
# S_trim = S without first element:
# {(),(2),(3),(2,3)}
# S_trim concatenated with first element:
# {(1),(1,2),(1,3),(1,2,3)}
# we keep the character sliced from front and concat it 
# with result of recursion

# use map to apply concatenation to all output from powerset

leading = (input[0])
new_input = input[1:len(input)]


ps1 = list((powerSet(new_input)))
# concatenate over powerset-ed set
ps2 = map(lambda x: [leading]+x,ps1) 

ps_list = list(map(lambda x: list(x),ps2))

return ps1+ ps_list    

Answer 7

Continuing on the answers provided by @Miguel and @Abdul...the following function insures a lexicographically ordered output.

def subset(A):
    if A == []:
        return [[]]
    sub = subset(A[:-1])
    return sub + [rem + [A[-1]] for rem in sub] 

tests = [[], [1], [1,2], [1,2,3]]
for test in tests:
    print(subset(test))

RESULT

[[]]
[[], [1]]
[[], [1], [2], [1, 2]]
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]