Search code examples
pythonalgorithmlist-comprehensionpowersetloop-unrolling

How to unroll a list comprehension


I have the following code I am trying to understand as I am new to Python. I understand that the code computes the powerset but the line subsetlist = [ subset + [item] for subset in result] is a little hard to understand. How can I break this compounded line to simple for loop for understanding.

def powerset(x):
    result = [[]]
    for item in x:
        subsetlist = [ subset + [item] for subset in result]
        result.extend(subsetlist)
    return result

This is what I have tried to make it simpler but it does not seem to work. My IDLE just gets stuck and does not print anything.

def powerset(x):
    result = [[]]
    for item in x:
        for subset in result:
            result.append(item)
    print(result)

Solution

  • Hint:

    You were very close. Just move the empty list creation inside the second loop.

    Working code:

    def powerset(x):
        result = [[]]
        for item in x:
            subsetlist = []
            for subset in result:
                subsetlist.append(subset + [item])
            result.extend(subsetlist)
        return result
    

    Output from IDLE:

    >>> powerset('abc')
    [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]