CODEWITHSUNDEEP
pythonalgorithmrecursionpowerset
ben348943
ben348943

Reputation: 51

Generating Power Set with Recursion and Yield Statement in Python

I am a bit new to Python and am working through programming exercises. I have written the following recursive method to generate the power set based on an input list in Python. It should return a generator that generates the power set of a given list passed in as s. Each element in the power set should be a set.

def gps(s, res=set()):
    if s:
        elem = s.pop()
        gps(s, res)
        res.add(elem)
        gps(s, res)
    else:
        yield res

When I call it using list(gps([1,2])) however it gives me []. The correct result should be something like [set(), {1}, {2}, {1, 2}].

I removed the yield statement, added two lines of code and played around with print statements to get this code, which prints the right results and seems like a step closer:

def gps(s, res=set()):
    if s:
        elem = s.pop()
        gps(s, res)
        res.add(elem)
        gps(s, res)
        s.append(elem)
        res.remove(elem)
    else:
        print(res)

After reading another Stack Overflow answer I modified my function to use yield from but the modified code below still gives me incorrect results:

def gps(s, res=set()):
    if s:
        elem = s.pop()
        yield from gps(s, res)
        res.add(elem)
        yield from gps(s, res)
        s.append(elem)
        res.remove(elem)
    else:
        yield res

Where am I going wrong with my approach? Any tips and clarifications would be appreciated.

Upvotes: 4

Views: 833

Answers (3)

blhsing
blhsing

Reputation: 106465

For a recursive approach, as the title of the question suggests, you can make the function take out the first item of the input sequence and then recursively yield each subset from the powerset of the rest of the sequence, with and without the first item added:

def powerset(seq):
    if seq:
        first, *rest = seq
        for subset in powerset(rest):
            yield subset
            yield {first, *subset}
    else:
        yield set()

so that list(powerset([1, 2])) returns:

[set(), {1}, {2}, {1, 2}]

and that list(powerset([1, 2, 3])) returns:

[set(), {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}]

Since the time complexity of unpacking in first, *rest = seq in the above code (or slicing, in the case of nums[1:] in @DanielHao's answer) is O(n), you can improve the time complexity of the step to O(1) by creating an iterator from the input sequence first so that you can fetch the next item from the sequence in constant time at each recursion level:

def powerset(seq):
    def _powerset(seq):
        try:
            first = next(seq)
            for subset in _powerset(seq):
                yield subset
                yield {first, *subset}
        except StopIteration:
            yield set()

    yield from _powerset(iter(seq))

Upvotes: 0

Daniel Hao
Daniel Hao

Reputation: 4980

Maybe you could try this code, without any built-in methods.

def subset(nums):
    ans = [[]]

    for n in nums:
        ans += [a+[n] for a in ans]

    return ans


nums = [1, 2, 3]

print(subset([1,2,3]))  # [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Or you still prefer the generator version:

def powerset(nums):
    """
    This is a generator version
    """
    if len(nums) <= 1:
        yield nums
        yield []
    else:
        for x in powerset(nums[1:]):
            yield [nums[0]]+ x
            yield x



if __name__ == '__main__':
    nums = [1, 2, 3]
    print(list(powerset(nums)))

Upvotes: 3

Iain Shelvington
Iain Shelvington

Reputation: 32244

itertools.combinations can be used to to get all combinations of elements in the list of a certain length. To get the powerset you can combine all combinations of length 0 with all of length 1 and so on up to the length of the list

import itertools

s = [1, 2]
result = []

for x in range(len(s) + 1): 
    result.extend(map(set, itertools.combinations(s, r=x)))

print(result)  # [set(), {1}, {2}, {1, 2}]

The original input should really be a set or at least have unique values, if the list has duplicates this may not work as the input was not a "set"

Upvotes: 0

Related Questions