0

I'm given a list, for example: [2,5,8] and a value c, for example, 33. So, because the length of the list is 3, I have to return a list of tuples (i,j,k) for which i*w[0] + j*w[1] + k*w[2] == c (33).

Of course, this is easily solved with 3 for loops, as shown:

res = []
for i in range(c+1):
   for j in range(c+1):
       for g in range(c+1):
           if i*self.w[0] + j*self.w[1] + g*self.w[2] == c:
              res.append((i,j,g))
return sorted(res)

The output will be:

[(0, 5, 1), (1, 3, 2), (2, 1, 3), (4, 5, 0), (5, 3, 1), (6, 1, 2), (9, 3, 0), (10, 1, 1), (14, 1, 0)]

The problem is that I have to do this with lists with other lengths as well. So my question is; does anyone know how to do this in general, for a list with length x (not too big) and a given value c?

Mrinal Roy
  • 969
  • 7
  • 12
Stijn Oosterlinck
  • 3
  • 2
  • looks like your question might be related to: https://stackoverflow.com/questions/8371887/making-all-possible-combinations-of-a-list – jmunsch Jul 28 '20 at 19:41
  • Does this answer your question? [Making all possible combinations of a list](https://stackoverflow.com/questions/8371887/making-all-possible-combinations-of-a-list) – jmunsch Jul 28 '20 at 19:42

2 Answers2

1

Using itertools.product and operator.mul:

>>> [k for k in product(range(c+1), repeat=len(w)) if sum(map(mul, w, k)) == c]
[(0, 5, 1), (1, 3, 2), (2, 1, 3), (4, 5, 0), (5, 3, 1), (6, 1, 2), (9, 3, 0), (10, 1, 1), (14, 1, 0)]
superb rain
  • 5,300
  • 2
  • 11
  • 25
  • Nice. I hadn't realised that `map` can take more than one iterable. That's another useful thing you've taught me today. – alani Jul 28 '20 at 19:59
  • thanks for your answer! I was wondering if you know how to do this without using itertools and map because we didn't learn that at school so we're not allowed to use that kind of tools – Stijn Oosterlinck Jul 28 '20 at 20:06
  • @StijnOosterlinck Then perhaps recursion. Or, depending on the data specification, dynamic programming. – superb rain Jul 28 '20 at 20:08
  • hmm okay maybe its useful to understand this code because it simplifies the problem a lot, can you explain a little bit more what you're doing in the oneliner? – Stijn Oosterlinck Jul 28 '20 at 20:11
0

You can use itertools.product and zip to generalise here:

import itertools
w = [3,1,2,5]
c = 33
l = [range(c + 1)] * len(w)
res = []
for values in itertools.product(*l):
    if sum(a * b for a, b in zip(w, values)) == c:
        res.append(values)
print(sorted(res))

The loop that builds up res could be replaced by a list comprehension if desired. That is to say:

res = [values for values in itertools.product(*l)
           if sum(a * b for a, b in zip(w, values)) == c]
alani
  • 12,573
  • 2
  • 13
  • 23