0

I was given a weird task to find a product mix out of 33 different products to make a certain total sales value. The possible combination apparently is 2^33. When I used the code below it says "Memory Error". My win10 desktop has 64G memory installed. Good news is that I solved this problem by using Excel VBA, it took few hours to get the result. Does anyone has ideas to deal with this type of problem? Using a generator? or a PD dataframe? Thanks!

import numpy as np
import itertools, sys

a1 = [4435.48, 327.96, 23.26, 4136.78, 77.06, 158.73, 1389.34,
  820.32, 888.33, 3735.7, 201.78, 31.17, 250.04, 87.17, 3230.95,
  491.53, 47.11, 508.22, 52.22, 1255.98, 3755.11, 948.4, 905.44,
  80.41, 1323.68, 528.57, 1474.4, 83.98, 756.87, 310.68, 27.86,]
n = len(a1)
lst = [list(i) for i in itertools.product([0, 1], repeat=n)]

for g in lst:
    c = sum(np.multiply(g, a1))
    if abs(c - 11833) < 1:
        print (g)
        sys.exit()
juanpa.arrivillaga
  • 88,713
  • 10
  • 131
  • 172
LarryZ
  • 107
  • 2
  • 11
  • 2
    `itertools.product` *is* an iterator - the problem is that you're wrapping it in a list comprehension. Use it iteratively and you shouldn't hit the memory issue. – match Mar 08 '19 at 17:18
  • You have a variant of the [change-making problem](https://en.wikipedia.org/wiki/Change-making_problem), and solutions do not require brute-forcing all combinations. – Martijn Pieters Mar 08 '19 at 17:21
  • @juanpa.arrivillaga - quite right - just in time for me to edit :) – match Mar 08 '19 at 17:21
  • Thanks Guys! I am super new to Python. "Use it iteratively" Can you elaborate a little bit? @match. – LarryZ Mar 08 '19 at 17:25
  • @LarryZ don't materialize a list out of your `product` iterator, i.e. you did `lst = [list(i) for i in itertools.product([0, 1], repeat=n)]` you *don't need a list*, you want to iterate over the values in the iterator. Literally replace that line with `lst = itertools.product([0, 1], repeat=n)` and maybe choose another name other than `lst` since it isn't a list. – juanpa.arrivillaga Mar 08 '19 at 17:26
  • The way to solve this class of problems is to use *dynamic programming*, see http://interactivepython.org/courselib/static/pythonds/Recursion/DynamicProgramming.html for a good overview. – Martijn Pieters Mar 08 '19 at 17:27
  • If you need to do similiar stuff again, try linear programming. Scipy has scipy.optimize.linprog for setting linear constraints etc. Do you use an 32 bit python installation? – Jay-Pi Mar 08 '19 at 17:30
  • I'm using 64bit annoconda @ Jay-Pi – LarryZ Mar 08 '19 at 17:32
  • @juanpa.arrivillaga Thanks for the detailed explanation for a new bee. :) – LarryZ Mar 08 '19 at 18:01
  • Follow-up: @juanpa.arrivillaga I changed the code as you suggested. lst = itertools.product([0, 1], repeat=n). it is still apparaently a brute-force, BUT It gives me the answer less than 2-3 seconds!!! Why is that? I didn't do any of the dynamic programming stuff as all. Does "np.multiply" do any magic? Just curious. Thanks! – LarryZ Mar 08 '19 at 19:22
  • @LarryZ no. In fact, `np.multiply` is overkill here, you could just do it in vanilla Python. This is the difference between materializing a giant list and iterating over the value's lazily. Now, you aren't escaping the O(2^n) time complexity here, you simply avoided the O(2^n) space complexity, which was preventing you from even trying to run it. You will see the effects of combinatorial explosion quite rapidly as you increase N. – juanpa.arrivillaga Mar 08 '19 at 19:40

1 Answers1

-1

Memory means that you ran out of memory. You can check by import sys; print(sys.maxsize) or import struct; print(struct.calcsize("P")*8). The latter is the check for 32bit or 64bit.

Jay-Pi
  • 343
  • 3
  • 13