CODEWITHSUNDEEP
pythonrecursionsubset
thisisName
thisisName

Reputation: 45

How to use recursion to get subset by splitting the set to first one and rest part (python)

I want to write a function using recursion to get the subset of a set and print like this when we input[1, 2, 3]as set:

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

My thinking is split the set to two part, the first one, and the rest. Then use the first one to append the every element in the rest list.

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

It doesn't work. How can I fix it?(only allow one parameter,set)

Upvotes: 3

Views: 353

Answers (4)

PM 2Ring
PM 2Ring

Reputation: 55479

I guess generating the powerset is a nice exercise in recursion, but it's generally better to do things iteratively if you can; Python doesn't have any optimisations for recursion.

It's possible to do powersets with a one-liner, using reduce, but since Guido doesn't like reduce I'll do 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 manually wrapped the output to avoid scrolling).

Upvotes: 2

sujoy
sujoy

Reputation: 135

I think dreyescat gave the right answer. Check the code below to find out where your code went wrong compared to his, unless you have already figured it out :-).

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

Upvotes: 1

dreyescat
dreyescat

Reputation: 13818

Assuming that the elements doesn't have any 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 exactly in the same order as you require:

[[], [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 output:

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

Upvotes: 3

AMacK
AMacK

Reputation: 1396

I believe this should do the trick, although I should probably be asleep 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 w/o 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 bit clunky, though.

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

Upvotes: 2

Related Questions