Permutation for equation solving

Question

If there is an equation 3a + 6b +7d = 55 and the solution set is {1,4,6} but it is unknown which number in the solution corresponds to which variable, is there a way to determine which number corresponds with which variable without using brute force? Could this method scale if the equation had 1000 variables? Thanks!

Answer 1

This is brute-force solution with pruning search where solution can't be found.

Let's show two things. First, if coefficients and solutions are non-negative numbers and if they are represented as a sorted list, then maximal value equation can have is 'parallel sum', and minimal value is 'reversed sum'.

max = sum(c*s for c, s in zip(coeffs, sols))
min = sum(c*s for c, s in zip(coeffs, reversed(sols)))

It is enough to see that for four numbers 0 <= a1 <= a2 and 0 <= b1 <= b2 holds:

a1*b1 + a2*b2 = a1*b2 + a2*b1 + (a2-a1)*(b2-b1) >= a1*b2 + a2*b1.

Second is that it is always possible to transform problem to problem of the same type with non-negative coefficients and solutions. To 'move' solutions to non-negative it is needed to add to all solutions value -min(solutions) and to result -min(solutions)*sum(coefficients). Similar procedure 'moves' coefficients to non-negative.

Here is python implementation of solution:

def C(coeffs, res, sols):
    _max = sum(i*j for i, j in zip(coeffs, sols))
    if _max < res:   # No result
        return None
    if _max == res:  # Result mapping coeffs <-> sols
        return sols
    _min = sum(i*j for i, j in zip(coeffs, reversed(sols)))
    if _min > res:   # No result
        return None
    if _min == res:  # Result mapping coeffs <-> reversed sols
        return sols[::-1]  # reverse sols
    # For next coefficient try all solutions
    for i, s in enumerate(sols):
        r = C(coeffs[1:], res - coeffs[0]*s, sols[:i] + sols[(i+1):])
        if r is not None:
            return [s] + r

print C([3, 6, 7], 55, [1, 4, 6])