CODEWITHSUNDEEP
pythonpython-3.xrefactoringpermutation
Purushothaman U
Purushothaman U

Reputation: 69

How to reduce the memory consumed by itertools.product?

I am trying to generate all the permutations of a range of numbers(a,b) of size k and count the number of permutations whose sum is even. Currently my code is

highLow = [int(i) for i in input().split()]
k = int(input())
permutations = list(product(list(range(highLow[0],highLow[1]+1)), repeat=k))
print(len(list(filter(lambda x:sum(x)%2 == 0, permutations))))

But this is giving me a memory limit exceeded. How to solve this memory problem?

Upvotes: 0

Views: 346

Answers (2)

superb rain
superb rain

Reputation: 5521

As chepner answered, product uses only O(1) memory. You can also solve your problem with O(0) memory for product, though, by not using product at all.

For example, the answer for low, high = 1, 99 and k = 100 is 18301617063661475246530801328625869309485603831946184570297868634965852237536237409359827175501347520033078455032642163735911784840089970792855267724585378713694517503049135418557489109958380424745001. With that method of filtering/counting product, that would take an eternity. With a little math, I computed that in less than a millisecond.

Yeah, this doesn't exactly answer the question as asked, but addresses the actual task. It's so common that people try to go through all permutations/combinations when they really shouldn't, that I think this is a useful answer.

Upvotes: 0

chepner
chepner

Reputation: 531325

product uses O(1) memory; it's only your use of list to create a list of all the values that uses so much memory.

low, high = [int(i) for i in input().split()]
k = int(input())
permutations = product(range(low, high + 1), repeat=k)
n = sum(1 for _ in filter(lambda x: sum(x) % 2 == 0, permutations))
print(n)

Upvotes: 2

Related Questions