3

You're solving a simple Diophantine equation and you use the following Python code to do it.

## 3a+b+c+d=10

r=10/3
for a in range(r, 0, -1):
    r=10-3*a
    for b in range(r, 0, -1):
        r=10-3*a-b
        for c in range(r, 0, -1):
            d=10-3*a-b-c
            if d>0:
                print a, b, c, d, 3*a + b + c + d

While preserving the essential character of the code how would you represent it 'nicely' so that it extends to provide for more variables in the Diophantine equation?

There are nine solutions:

1 6 1

1 5 2

1 4 3

1 3 4

1 2 5

1 1 6

2 3 1

2 2 2

2 1 3

Bill Bell
  • 21,021
  • 5
  • 43
  • 58
  • 1
    The code you provided prints something different from the nine solutions you listed. – dano Apr 19 '15 at 16:36

2 Answers2

4

I would create a recursive generator function where the arguments are the total sum s and the multipliers for each element:

def solve(s, multipliers):
    if not multipliers:
        if s == 0:
            yield ()
        return
    c = multipliers[0]
    for i in xrange(s // c, 0, -1):
        for solution in solve(s - c * i, multipliers[1:]):
            yield (i, ) + solution

for solution in solve(10, [3, 1, 1]):
    print solution

Result:

(2, 3, 1)
(2, 2, 2)
(2, 1, 3)
(1, 6, 1)
(1, 5, 2)
(1, 4, 3)
(1, 3, 4)
(1, 2, 5)
(1, 1, 6)
JuniorCompressor
  • 19,631
  • 4
  • 30
  • 57
1

You can define the possible values of each variable first and then iterate over all possible combinations using itertool's product:

from itertools import product

## 3a+b+c+d=10

A = range(10, 0, -1)
B = range(10, 0, -1)
C = range(10, 0, -1)

for a, b, c in product(A, B, C):
    d = 10 - 3 * a - b - c
    if d > 0:
        print a, b, c, d, 3 * a + b + c + d

Output:

2 2 1 1 10
2 1 2 1 10
2 1 1 2 10
1 5 1 1 10
1 4 2 1 10
1 4 1 2 10
1 3 3 1 10
1 3 2 2 10
1 3 1 3 10
1 2 4 1 10
1 2 3 2 10
1 2 2 3 10
1 2 1 4 10
1 1 5 1 10
1 1 4 2 10
1 1 3 3 10
1 1 2 4 10
1 1 1 5 10

Note that by using the same r for all loops you're doing more work than actually necessary. So it depends on the application, whether this solution helps or not.

Falko
  • 17,076
  • 13
  • 60
  • 105
  • I don't think this gives the correct answer. Not all the for loops start with the same `r` value. – dano Apr 19 '15 at 16:30
  • @dano: Oh, I overlooked the different `r`... Need to rethink the answer. – Falko Apr 19 '15 at 16:33
  • It's not that you're doing extra work, it's that it's missing possible solutions. The problem is that `r` for an inner loops gets recalculated after every iteration of its outer loop, so the second time through `B`, `r` isn't `1` anymore, it's `4`. The next time, it's `7`. If you compare your output to the code in the question, there's several missing answers. – dano Apr 19 '15 at 16:41
  • @dano: Ok, I see. I'd need to run from 10 down to 1 for each variable. But I don't get why (1,1,1,5) shouldn't be a solution to 3a+b+c+d=10. – Falko Apr 19 '15 at 16:52
  • `(1,1,1,5)` is a solution, but so is `(1,5,1,1)`, and `(1,1,5,1)` which are missing. You just don't have all the possible solutions. None of the solutions in your output are wrong, it's just incomplete. – dano Apr 19 '15 at 16:55
  • @dano: Yeah, I updated my answer respectively. It's not as elegant as I hoped it to be, but at least I'm not missing solutions anymore. – Falko Apr 19 '15 at 16:56