2
$\begingroup$

Consider the linear Diophantine equation of the form: $$\sum_{i=1}^{k}a_ix_i=n.$$ My goal is to list all the non-negative solutions to this equation. I wrote the following recursive algorithm, but I am not sure if it is the most efficient way to build the solutions. Here is the current version:

def recsolve(n, L, cursol, result = []):
if len(L) == 1:
    ak = L[0]
    if n%ak == 0:
        result.append(cursol + [n//ak])
    return

else:
    a1 = L[0]
    end = math.floor(n/a1)
    for k in range(0, end + 1):
        recsolve(n-k*a1,L[1:], cursol + [k],result)


result = []
n = 5
L = [1,2,3]
recsolve(n, L, [], result)
print(result, "; Number of solutions:", len(result))

I would be grateful if someone could suggest more efficient approaches to finding all solutions to a linear Diophantine equation.

$\endgroup$
1
$\begingroup$

Your current recursive solution is pretty solid. It is, I believe, about the most efficient recursive approaches we can have for the general situation.

Somehow I prefer the code in you first solution since it is easier to read. All we need to make it correct is to change return [None] to return [] and if None not in res: to if res:

Implementation-wise, we could change it to use an iterative method which should run faster. Also, we could sort $a_i$ in descending order which may improve the listing speed. For example, solutions for $100x_1+100x_2+x_3=1000$ will be found much faster than $x_1+100x_2+100x_3=1000$.

In some special cases, we might be able to speed up the performance. For example, for $15x_1+10x_2+6x_3=100000$, $x_1$ must be a multiple of 2, $x_2$ must be a multiple of 3, $x_3$ must be a multiple of 5. These restriction could help us to improve the speed if they are given or they can be found by factorization easily.

$\endgroup$
0
$\begingroup$

You can use dynamic programming. For each $j \leq k$ and $m \leq n$, find the number of solutions to $$ \sum_{i=1}^j a_i x_i = m. $$ Details left to you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.