def powerset(x):
total1 = [[]]
total2 = [[]]
for a in x:
for b in total1:
c = list(b + [x[a]])
total2.append(c)
total1 = total2
# the total 1 and total 2 system should prevent it
# from creating an infinite loop when we add to the total.
print (total1)
f = [1,2,3]
g = powerset(f)
print (g)
Here is my attempt at creating a powerset for an intro to data science class. When I run this I receive [[], [2]] as outputs before running out of memory. I don't understand why it it returns [[], [2]] nor why it runs out of memory, since total1 is changed outside of the loop.
The variable g should return a power set of f.
Could somebody explain what I'm doing wrong?
After the first loop you set total1 = total2, so that means that total1 and total2 refer to the same list.
And so in the second loop, you iterate over total1 and update total2, the same list. In Python (and in most programming languages) it is dangerous to alter a collection you iterate over, so you keep adding items to the list, making the loop longer and longer.
The code is not per se problematic. We can write it as:
def powerset(x):
result = [[]]
for xi in x:
xil = [xi]
for j in range(len(result)):
result.append(result[j] + xil)
return result
Although it may look like some syntactical rewrites, we here iterate j over the range(len(result)). Note that we calculate len(result) only once, when we start the for loop, so after that, we can safely update total, since the range object does not change anymore.
This then yields:
>>> powerset([1,2,3])
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Notice that we can use the itertools.combinations function to make life easier:
from itertools import combinations
def powerset(x):
xl = list(x)
for r in range(len(xl)+1):
for ri in combinations(xl, r):
yield ri
We then obtain:
>>> list(powerset([1,2,3]))
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]