Posts: 28
Threads: 11
Joined: Jul 2021
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
Posts: 6,798
Threads: 20
Joined: Feb 2020
Feb-05-2022, 05:13 AM
(This post was last modified: Feb-05-2022, 05:13 AM by deanhystad.)
"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.
Posts: 28
Threads: 11
Joined: Jul 2021
(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!
Posts: 6,798
Threads: 20
Joined: Feb 2020
Feb-05-2022, 06:00 PM
(This post was last modified: Feb-05-2022, 06:01 PM by deanhystad.)
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)
|