How to store same value in two variables while independently changing them both in python?

Question

I am trying to create a recursive function that returns the set of all non-empty subset of [1,2,3,...,n] numbers.

Here is my code:

def subsets(n):
    if n == 2:
        return ([1], [2], [1, 2])
    else:
        previous = subsets(n - 1)
        temp = previous
        result = ()
        for set in previous:
            set += [n]
            result += (set,)
        return temp + ([n],) + result

this doesn't work as temp stores the value of previous after it has been modified. Simply changing it to-

previous = subsets(n - 1)
temp = subsets(n - 1)

works but is obviously not a very efficient solution. I have also tried-

previous,temp = subsets(n - 1)

but this raises a "too many values to unpack" error. What do I do?

For `previous,temp = subsets(n - 1)` to work, `subsets` has to return two values, but it does not. — zvone, May 19 '18 at 23:42
See [Powersets in Python using itertools](https://stackoverflow.com/q/18035595/674039) — wim, May 19 '18 at 23:48
i changed the return to a tuple of two exact same values but it only worked for subsets(3) when doing subsets(4) it gives back the same "too many values to unpack" error — Zero, May 19 '18 at 23:49
As a quick fix you could use `temp = copy.deepcopy(previous)`. — Paul Panzer, May 19 '18 at 23:52
Or even better: don't change `set` in place. Leaving complaints about shadowing builtin names to one side, try `set = set + [n]` in the loop. — Paul Panzer, May 20 '18 at 00:00
thanks a ton paul! Both your answers work perfectly. I had no idea doing x=x+n is different from x+=n — Zero, May 20 '18 at 00:06

Olivier Melançon · Answer 1 · 2018-05-20T12:28:16.317

1

I want to point out that returning all subsets is something you can accomplish efficiently with itertools.

import itertools

def subsets(n):
    for x in range(1, n + 1):
        yield from itertools.combinations(range(1, n + 1), x)

print(*subsets(3))  # (1,) (2,) (3,) (1, 2) (1, 3) (2, 3) (1, 2, 3)

This returns a generator which will save a lot of memory since a power set grows exponentially.

edited May 20 '18 at 12:28

answered May 20 '18 at 00:07

Olivier Melançon

21,584
4
41
73

This is the way to go! – Gwang-Jin Kim May 20 '18 at 08:09

Gregoire Lodi · Answer 2 · 2018-05-19T23:59:57.573

0

Since you're returning a tuple, Python return its reference. That's why when you change previous, temp changes as well.

To store them independently, you may use the slice operator:

previous = subsets(n - 1)
temp = previous[:]

Using [:] will copy previous content to temp instead of assigning previous reference to temp.

EDIT:

When you have some nesting inside your data structure, you would have to use a deepcopy:

import copy # at the top of your script

previous = subsets(n - 1)
temp = copy.deepcopy(previous)

Thanks to @Paul Panzer for pointing that out in the comments.

edited May 19 '18 at 23:59

answered May 19 '18 at 23:51

Gregoire Lodi

557
2
10

A shallow copy as created by slicing is not enough here. You need a deep copy. – Paul Panzer May 19 '18 at 23:56
doesn't work, it returns the exact same output as temp = previous – Zero May 19 '18 at 23:58
As @PaulPanzer pointed out, you'd need a deep copy. I've edited my answer to reflect that. – Gregoire Lodi May 20 '18 at 00:00

score 0 · Answer 3 · answered May 20 '18 at 00:00

What you need is a deep copy of previous, not just another reference (temp = previous) nor a shadow copy (temp = previous[:]).

previous = ([1],)
temp = previous[:]
myset = previous[0]
myset += [2]
print(previous)  # ([1, 2],) 
print(previous)  # ([1, 2],)

What you can do:

for set in previous:
    set = list(set)  # make a copy
    set += [n]
    result += (set,)

score 0 · Answer 4 · answered May 20 '18 at 00:29

The minimal change to you code would probably be to not modify set with set += ([n], ), but to create a new tuple with set + ([n], ). temp is unused then and can be removed. Full code:

def subsets(n):
    if n == 2:
        return ([1], [2], [1, 2])
    else:
        previous = subsets(n - 1)
        result = ()
        for set in previous:
            result += (set + [n],)
        return previous + ([n],) + result

Because result += ... creates a new tuple each time, this is not efficient and should be replaced by a generator expression:

def subsets(n):
    if n == 2:
        return ([1], [2], [1, 2])
    else:
        previous = subsets(n - 1)
        return previous + ([n],) + tuple(set + [n] for set in previous)

How to store same value in two variables while independently changing them both in python?

4 Answers4