Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
shallowcopy of an object
#1
Can somebody explain to me why in the following code, temp is equal to res after the loop body statement? I have tested it with input [1] and after the loop executes temp is as I said equal to the new res. Also, res = res + temp does not produce the expected [[1],[]] but [[1]].
Can somebody explain this to me as well?

def driver(arr):
    res = [[]]
    def subsets(arr,res):
        if arr == []:
            return
        subsets(arr[1:],res)
        temp = res
        #here temp = [[]] for the inner most function call
        for subset in res:
            subset.append(arr[0])
        #but here temp = res if one tries for instance the input [1]
        res = res + temp
    subsets(arr,res)
    return res
Reply
#2
"res = [[]]" creates a variable local to driver(). "res = res + temp" creates a variable local to subsets(). Not only are these different variables, but they reference different lists. The list returned by driver is not the list being modified in subsets(). This is shown if you print out the object ID for res.
def driver(arr):
    res = [[]]

    def subsets(arr, res):
        print("res is a variable passed into subsets as", id(res))
        if arr == []:
            return
        subsets(arr[1:],res)
        temp = res
        #here temp = [[]] for the inner most function call
        for subset in res:
            subset.append(arr[0])
        res = res + temp
        print("assignment of res inside subsets creates a local array", id(res))

    print("res starts out as", id(res))
    subsets(arr, res)
    return res

res = driver([1])
print("The res returned by driver is the res defined in driver, not subsets", id(res))
Output:
res starts out as 2255377308416 res is a variable passed into subsets as 2255377308416 res is a variable passed into subsets as 2255377308416 assignment of res inside subsets creates a local array 2255377308352 The res returned by driver is the res defined in driver, not subsets 2255377308416
temp = res does not make temp a copy of res, not even a shallow copy. Assignment creates a new variable, but the variable references the same list as res. "res = res + temp" is exactly the same as "res = res + res". Not only do you want to copy, I think you want a deep copy.

Is this what you are looking for?
import copy

def driver(arr):
    res = [[]]

    def subsets(arr, res):
        if arr == []:
            return
        subsets(arr[1:], res)
        temp = copy.deepcopy(res)
        #here temp = [[]] for the inner most function call
        for subset in res:
            subset.append(arr[0])
        res[:] = res + temp

    subsets(arr, res)
    return res

print(driver([1, 2, 3]))
Output:
[[3, 2, 1], [2, 1], [3, 1], [1], [3, 2], [2], [3], []]
If I understood what you wanted to accomplish I might know a better way to do it. For example, this code achieves the same thing (almost).
def subsets(values):
    results = [[]]
    for value in values:
        for subset in results[:]:
            results.append([value] + subset)
    return results

print(subsets([1, 2, 3]))
Output:
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1]]
And if a list of combinations is all you want there are functions in the itertools library that will do this shorter and faster.
Reply
#3
(Feb-05-2022, 05:13 AM)deanhystad Wrote: "res = [[]]" creates a variable local to driver(). "res = res + temp" creates a variable local to subsets(). Not only are these different variables, but they reference different lists. The list returned by driver is not the list being modified in subsets(). This is shown if you print out the object ID for res.
def driver(arr):
    res = [[]]

    def subsets(arr, res):
        print("res is a variable passed into subsets as", id(res))
        if arr == []:
            return
        subsets(arr[1:],res)
        temp = res
        #here temp = [[]] for the inner most function call
        for subset in res:
            subset.append(arr[0])
        res = res + temp
        print("assignment of res inside subsets creates a local array", id(res))

    print("res starts out as", id(res))
    subsets(arr, res)
    return res

res = driver([1])
print("The res returned by driver is the res defined in driver, not subsets", id(res))
Output:
res starts out as 2255377308416 res is a variable passed into subsets as 2255377308416 res is a variable passed into subsets as 2255377308416 assignment of res inside subsets creates a local array 2255377308352 The res returned by driver is the res defined in driver, not subsets 2255377308416
temp = res does not make temp a copy of res, not even a shallow copy. Assignment creates a new variable, but the variable references the same list as res. "res = res + temp" is exactly the same as "res = res + res". Not only do you want to copy, I think you want a deep copy.

Is this what you are looking for?
import copy

def driver(arr):
    res = [[]]

    def subsets(arr, res):
        if arr == []:
            return
        subsets(arr[1:], res)
        temp = copy.deepcopy(res)
        #here temp = [[]] for the inner most function call
        for subset in res:
            subset.append(arr[0])
        res[:] = res + temp

    subsets(arr, res)
    return res

print(driver([1, 2, 3]))
Output:
[[3, 2, 1], [2, 1], [3, 1], [1], [3, 2], [2], [3], []]
If I understood what you wanted to accomplish I might know a better way to do it. For example, this code achieves the same thing (almost).
def subsets(values):
    results = [[]]
    for value in values:
        for subset in results[:]:
            results.append([value] + subset)
    return results

print(subsets([1, 2, 3]))
Output:
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1]]
And if a list of combinations is all you want there are functions in the itertools library that will do this shorter and faster.

Sorry for replying late, I was trying to write a function that computes the powerset for a given input array. Thanks for your answer!
Reply
#4
Don't use the reply button. It is annoying having to scroll down a bunch of duplicated posts.

Here is a solution that uses itertools combinations. It is a generator, so it only makes the subsets one at a time
import itertools

def powerset(values):
    """Generate subsets of values."""
    for length in range(len(values)+1):
        for subset in itertools.combinations(values, length):
            yield subset

for subset in powerset((1, 2, 3)):
    print(subset)
Output:
() (1,) (2,) (3,) (1, 2) (1, 3) (2, 3) (1, 2, 3)
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020