Powerset algorithm in Python: difference between + and append on lists

44
December 03, 2019, at 01:20 AM

I’m working through the powerset problem in Python.

The powerset P(S) of a set S is the set of all subsets of S. For example, if S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.

This solution works just fine:

def powerset(array):
    powerset = [[]]
    for num in array:
        for i in range(len(powerset)):
            curr_subset = powerset[i]
            powerset.append(curr_subset + [num])
    return powerset

However, this solution does not:

def powerset(array):
    powerset = [[]]
    for num in array:
        for i in range(len(powerset)):
            curr_subset = powerset[i]
            curr_subset.append(num)
            powerset.append(curr_subset)
    return powerset

It seems to overwrite every array in the powerset on each powerset.append operation. For an input of [1, 2, 3], I end up with a return value of:

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

Any idea what I’m not fully understanding here?

Answer 1

The problem with your algorithm is that lists are mutable, and you are creating a list full of references to the same list. Any time you append to one of them, you are appending to all of them, because there is only one of them. They are all the same list, you just have more than one reference to it.

Imagine having a list of 10 copies of somebody's phone number; if you call up the first phone number and ask them to put on a hat, then when you call the second phone number, the person on the other end will already be wearing a hat, because it is the same person. If you call each number and say "put on a hat" each time, you'll end up with a list of 10 phone numbers for one person wearing 10 hats, when you actually wanted phone numbers for 10 people wearing one hat each.

The simplest way to design this kind of algorithm is to avoid mutation completely; use tuples instead of lists. This way, every time you add on another element to the tuple, you are creating a new tuple instead of changing the existing one.

Note that this is quite similar to your first solution using curr_subset + [num]; the + operation creates a new list, unlike append which changes the state of an existing list.

def powerset(array):
    # a list containing an empty tuple
    powerset = [()]
    for num in array:
        for i in range(len(powerset)):
            curr_subset = powerset[i]
            # append one more number to the tuple
            curr_subset += (num,)
            powerset.append(curr_subset)
    return powerset

Example:

>>> powerset([1, 2, 3])
[(), (1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3)]
READ ALSO
Django - Multiple user types (ability to switch between them)

Django - Multiple user types (ability to switch between them)

I am doing some pre-planning on a project I am working on and my approach to itA part of the app is the ability to have multiple user types

52
Function to find number of 'ordered combinations' with no particular length of a list Python

Function to find number of 'ordered combinations' with no particular length of a list Python

While variants of this question have been asked numerous times on this site, I haven't found any information on how to do 'ordered combinations' with a given list

64
jQuery submit function add data several times

jQuery submit function add data several times

I have this function I use to store items (voucher codes) based on some rules

50
How to use a select's value to show a certain div(a div of radio buttons)?

How to use a select's value to show a certain div(a div of radio buttons)?

My goal: The user picks selection 1 and the corresponding div will showThe user picks selection 2, the selection 1 div disappears and shows the selection 2's div

73