Перестановки для решения уравнений

Question

Если есть уравнение 3a + 6b +7d = 55 и множество решений является {1,4,6} но неизвестно, какой номер в растворе соответствует какому переменному, есть ли способ, чтобы определить, какой номер соответствует какой переменной без с использованием грубого сила? Может ли этот метод масштабироваться, если уравнение имеет 1000 переменных? Благодаря!

Answer 1

Это решение грубой силы с обрезкой, где решение не найдено.

Давайте покажем две вещи. Во-первых, если коэффициенты и решения являются неотрицательными числами, и если они представлены как отсортированный список, то уравнение максимальной величины может иметь «параллельную сумму», а минимальное значение - «обратная сумма».

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

Достаточно заметить, что для четырех чисел 0 <= a1 <= a2 и 0 <= b1 <= b2 держит:

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

Во-вторых, что всегда можно превратить проблему в задаче того же типа с неотрицательными коэффициентами и решения. Чтобы «перевести» решения на неотрицательные, необходимо добавить к всем решениям значение -min(solutions) и привести к результату -min(solutions)*sum(coefficients). Аналогичная процедура «переводит» коэффициенты в неотрицательные.

Вот реализация питона решения:

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])