Generate a power set, but get an infinite loop

Python Help
1

I can generate the power set of nuts as follows:

def subsets(nums):
    res = [[], [nums[0]]]
    n = len(nums)
    for i in range(1,n):
        res += [x+[nums[i]] for x in res]
    return res

but I was wondering why the second method produces an infinite loop (it does not stop in 10 second with a length-3 nums)? I know it’s less efficient, but I wonder why it does not work:

def subsets(nums):
    res = [[], [nums[0]]]
    n = len(nums)
    for i in range(1,n):
        for x in res:
            res += [x +[nums[i]]]
            
    return res
2

It’s a question of how for x in res: works when res is a list. The iterator just keeps track of the current index in the list. These cause infinite loops:

>>> L = [0]
>>> for x in L:
...     L.append(x)
(infinite loop)
>>> for x in L:
...     L += [x]  # effectively the same
(infinite loop)

This is because, at each loop iteration, it checks whether you’ve gotten to the end of the list. But the list keeps on growing, so you never actually reach the end.

As a general rule of thumb, it’s usually nice to not modify any list that you’re currently iterating over. The list comprehension [x+[nums[i]] for x in res] creates its own list, all by itself, just by iterating over res without modifying res. Then, once that list comprehension has made this separate list, that whole new list gets passed to the += operator of res, which knows how to add in all of the items from the new list into res. There’s no infinite loop because you never iterate and modify the same list at the same time.

1 Like