3

The problem is to create a function to check if a linear combination of certain items of that list add up to a certain sum. The result would be a list with tuples(which are the same length of the list). For example: given list: [3,7,10], sum= 60 result: [(0, 0, 6), (1, 1, 5), (2, 2, 4), (3, 3, 3), (4, 4, 2), (5, 5, 1), (6, 6, 0), (10, 0, 3), (11, 1, 2), (12, 2, 1), (13, 3, 0), (20, 0, 0)] The problem is that the length of the list variates. I tried solving it with a bunch of if-statements and than using for loops, but there must be a more effective way to do it.

Here is some of the code I used.

def get_index(l, s):
    res = []
    if len(l)==3:
        for i in range(s+1):
                for j in range(s+1):
                    for k in range(s+1):
                        if l[0]*i + l[1]*j + l[2]*k==s:
                            res.append((i,j,k))
    return res

Thanks already!!

Note: It worked if I did changed the ranges to (s//l[i]+1).

Ehsan
  • 12,072
  • 2
  • 20
  • 33
V_Buffalo
  • 43
  • 6

2 Answers2

2

I feel like there is a better way to do it, but here is a brute-forth approach with arrays:

A = np.array([3,7,10])
b = np.array([60])

from itertools import product
combin = [np.arange(i) for i in (b//A)+1]
d = np.stack(list(product(*combin)))
[tuple(i) for i in d[d@A==b]]

or equivalently without itertools:

d = np.rollaxis(np.indices((b//A)+1),0,4).reshape(-1,3)
[tuple(i) for i in d[d@A==b]]

output:

[(0, 0, 6), (1, 1, 5), (2, 2, 4), (3, 3, 3), (4, 4, 2), (5, 5, 1), (6, 6, 0), (10, 0, 3), (11, 1, 2), (12, 2, 1), (13, 3, 0), (20, 0, 0)]

comparison:

#@Ehsan's solution 1
def m1(b):
  combin = [np.arange(i) for i in (b//A)+1]
  d = np.stack(list(product(*combin)))
  return [tuple(i) for i in d[d@A==b]]

#@Ehsan's solution 2
def m2(b):
  d = np.rollaxis(np.indices((b//A)+1), 0, 4).reshape(-1,3)
  return [tuple(i) for i in d[d@A==b]]

#@mathfux solution
def m3(b):
  A, B, C = range(0, b+1, 3), range(0, b+1, 7), range(0, b+1, 10)
  triplets = list(product(A, B, C)) #all triplets
  suitable_triplets = list(filter(lambda x: sum(x)==b, triplets)) #triplets that adds up to 60
  return [(a//3, b//7, c//10) for a, b, c in suitable_triplets]

performance:

in_ = [np.array([n]) for n in [10,100,1000]]

which makes m2 the fastest among them.

enter image description here

Ehsan
  • 12,072
  • 2
  • 20
  • 33
  • Yes I think it is a good idea to use arrays, but it doesn't solve my problem though. Thank you – V_Buffalo Aug 14 '20 at 15:44
  • @V_Buffalo It should be significantly faster than loops. Is the problem scalability of it? If so, how large are your arrays and how fast do you need this code to be? – Ehsan Aug 14 '20 at 16:00
  • The length of the given list are between 2 and 5. In jupyter notebooks your code and my was fine. But when I ran it through the program that my school uses to check the code it reaches the time limit with my code( with the if statements and for loops) and with your code the memory limit was exceeded. This is an exercise which I try to solve to prepare for my exam btw, not an assignment or anything. – V_Buffalo Aug 14 '20 at 16:17
  • Which kind of exam? If it's related with high school mathematics, we need an algorithm which is completely different :) – mathfux Aug 14 '20 at 16:23
  • It's a programming exam. It's actually an exercise about classes. The rest of my code is correct it is just this function within the class I can't seem to get right. – V_Buffalo Aug 14 '20 at 16:33
  • 1
    @V_Buffalo Use Sympy then. It probably has a fast and memory efficient solution. Also, I expect arrays to take use more memory than lists but be much more efficient. – Ehsan Aug 14 '20 at 16:37
  • yeah but I can't find any – V_Buffalo Aug 14 '20 at 16:55
  • @V_Buffalo I am not familiar with sympy. You can try the update on my post that might solve performance issue. – Ehsan Aug 14 '20 at 17:49
  • @Ehsan Unhappily, Sympy is not enough here because it is not able to identify domains of solutions. Only Sage can do it. – mathfux Aug 14 '20 at 21:52
2

This becomes a completely mathematical problem. You need to find all non-negative solution triplets for linear diophantine equation 3a+7b+10c=60.

The main idea of finding solutions for this equation can be illustrated using generating functions (polynomials). Let us take three such polynomials:

A=1+x^3+x^6+x^9+...+x^60
B=1+x^7+x^14+x^21+...+x^56
C=1+x^10+x^20+x^30+...+x^60

If you multiply them, you see that each term x^n can be expressed as a product of x^a, x^b and x^c, every of these terms are taken from A, B and C respectively.

Brute-force approach. You need to define multiplication of these polynomials that keeps track of terms that were multiplied, just like this:

[0, 3, 6] * [0, 7, 14] * [0, 10] = [(0,0,0), (0,0,10), (0,7,0), (0,7,10), (3,0,0), (3,0,10), (3,7,0), (3,7,10), (6,0,0), (6,0,10), (6,7,0), (6,7,10)]

Lists don't have * operator in Python but, fortunately, you can use itertools.product method instead. This is a complete sulution:

from itertools import product
A, B, C = range(0, 61, 3), range(0, 61, 7), range(0, 61, 10)
triplets = list(product(A, B, C)) # all triplets
suitable_triplets = list(filter(lambda x: sum(x)==60, triplets)) #triplets that adds up to 60
print([[a//3, b//7, c//10] for a, b, c in suitable_triplets])

Vectorised brut-force. This is based on previous script, replacing all the loops with numpy actions:

import numpy as np
l = np.array([3,7,10])
s = 60
unknowns = [range(0, s+1, n) for n in l]
triplets = np.stack(np.meshgrid(*unknowns), axis=-1).reshape(-1, len(unknowns))
suitable_triplets = triplets[np.sum(triplets, axis=1) == s]
solutions = suitable_triplets//l

Mathematical approach. In general, solving linear diophantine equations is hard. Look through this SO answer. It says that sympy is able to find a parametrised solution only but it can't identify domain:

import sympy as sp
from sympy.solvers.diophantine.diophantine import diop_solve
x,y,z = sp.symbols('x y z')
solution = diop_solve(3*x + 7*y + 10*z-60)

And the output of solution is (t_0, t_0 + 10*t_1 + 180, -t_0 - 7*t_1 - 120). Optimised solution is possible using Sage but you are required to download Linux Operating System in this case :D

mathfux
  • 5,759
  • 1
  • 14
  • 34
  • This is the same approach but less efficient compared to using arrays. – Ehsan Aug 14 '20 at 16:40
  • 1
    Yes, it's still brute-force. It can be optimised slightly in two ways: using `filter` after each product or using `numpy` as you did (because it uses C). If you need for essential update, an algebra of generating functions should be applied. – mathfux Aug 14 '20 at 16:52
  • I appreciate the help. – V_Buffalo Aug 14 '20 at 16:56
  • But In what way should i use Numpy? – V_Buffalo Aug 14 '20 at 16:56
  • You should try to replace all the list comprehensions, products, for loops and so one by `numpy` based actions. That's not always easy. This is pretty good example: `product(A, B, C)` is slow. It can be replaced by `np.stack(np.meshgrid(A, B, C), axis=-1).reshape(-1, 3)` – mathfux Aug 14 '20 at 17:04