Алгоритм для подмножества с вычитанием

Question

У меня есть проблема с подмножеством сумм, в которой вы можете добавить или вычесть условия. Например, если у меня есть пять членов (1, 2, 3, 4, 5), я хочу знать, сколько способов я могу добавить/вычесть условия, чтобы сделать 7:

• 3 + 4
• 2 + 5
• 1 + 2 + 4
• 5 - 2 + 4
• т.д.

Я написал код в Python, но это очень медленно, когда есть много терминов:

import itertools 
from collections import OrderedDict 

sum_answer = 1 
terms = {"T1": 1, "T2": -2, "T3": 3, "T4": -4, "T5": 5} 
numlist = [v for v in terms.values()] 
zerlist = [x for x in itertools.repeat(0, len(numlist))] 
opslist = [item for item in itertools.product((1, -1), repeat=len(numlist))] 


res_list = [] 
for i in range(1, len(numlist)): 
    combos = itertools.combinations(numlist, i) 

    for x in combos: 
     prnlist = list(x) + zerlist[:len(numlist) - len(x)] 

     for o in opslist: 
      operators = list(o) 
      result = [] 
      res_sum = 0 

      for t in range(len(prnlist)): 
       if operators[t] == 1: 
        ops = "+" 
       else: 
        ops = "-" 
       if prnlist[t] != 0: 
        result += [ops, list(terms.keys())[list(terms.values()).index(prnlist[t])]] 
       res_sum += operators[t] * prnlist[t] 

      if sum_answer == res_sum: 
       res_list += [" ".join(result)] 

for ans in OrderedDict.fromkeys(res_list).keys(): 
    print(ans) 

Я понимаю, что миллион вложенных циклов ужасно неэффективен, поэтому есть ли какие-то детали, которые я могу ускорить с лучшим алгоритмом?

Answer 1

Я думаю, что ваша идея в основном правильная: генерировать каждую комбинацию терминов, делать сумму и видеть, является ли это хитом. Однако вы можете оптимизировать свой код.

Проблема в том, что как только вы создаете 1 + 2, вы увидите, что это не соответствует вашей желаемой сумме и выбросить ее. Однако, если вы добавите к нему 4, это решение. Вы не доберетесь до этого решения, пока не сгенерируете 1 + 2 + 4, хотя при вычислении суммы с нуля. Вы также генерируете возможности добавления операторов с нуля для каждой комбинации, что также делает много избыточной работы по той же причине.

Вы также используете много списков операций, которые могут быть медленными.

Я хотел бы сделать это:

def solve(terms_list, stack, current_s, desired_s): 
    if len(terms_list) == 0: 
     if current_s == desired_s: 
      print(stack) 
     return 

    for w in [0, 1, -1]: # ignore term (0), add it (1), subtract it (-1) 
     stack.append(w) 
     solve(terms_list[1:], stack, current_s + w * terms_list[0], desired_s) 
     stack.pop() 

Первоначальный вызов, например, solve([1,2,3,4,5], [], 0, 7).

Обратите внимание, что это имеет сложность O(3^n) (вид, читайте дальше), поскольку каждый термин может быть добавлен, вычтен или проигнорирован.

Сложность моей фактической реализации - O(n*3^n), потому что рекурсивный вызов делает копию параметра terms_list. Однако вы можете избежать этого, но я хотел сделать код более простым и оставить это как упражнение. Вы также можете избежать создания фактического выражения перед его печатью и построить его поэтапно вместо этого, но для этого вам может потребоваться больше параметров.

Однако, O(3^n) все еще много, и вы не должны ожидать, что он будет очень хорошо работать для больших n независимо от того, что вы делаете.

Answer 2

Как «регулярная» проблема с подмножеством сумм - где вы используете DP для решения проблемы, вы также можете использовать ее здесь, но вам нужно будет иметь еще одну возможность - уменьшить текущий элемент вместо его добавления.

f(0,i) = 1    //successive subset 
f(x,0) = 0 x>0  //failure subset 
f(x,i) = f(x+element[i],i-1) + f(x-element[i],i-1) + f(x,i-1) 
           ^^^ 
       This is the added option for substraction 

При переводе его снизу вверх раствор DP, вам нужно будет создать матрицу размера (SUM+1) * (2n+1), где SUM является суммой всех элементов и n является числом элементов.

Answer 3

Прямо сейчас вы пытаетесь перетащить все возможные комбинации значений полей из одной строки (тогда проверка валидности каждой комбинации по отношению к другим строкам).

Предполагаю, что у вас есть много рядов данных для игры; Я предлагаю вам воспользоваться этим, взяв кучу строк (по крайней мере, столько, сколько у вас есть поля для решения) и применения приблизительного матричного решателя, такого как numpy.linalg.lstsq.

Это имеет ряд важных преимуществ:

• позволяет здраво решать проблемы округления ошибок (необходимо, если любой из ваших полей нецелая)

• позволяет легко обрабатывать поля, коэффициент которых не равен {-1, 0, 1}, т.е. налоговые ставки, коэффициент которых может быть примерно 0.12

• использует полностью поддерживаемый код, который вам не нужно отлаживать или maintai п

• использует высоко оптимизированный код, который будет работать значительно быстрее (**, скорее всего, в зависимости от того, какие варианты вашей NumPy был скомпилирован с)

• имеет безумно лучшее время сложность (что-то вроде O (N * * 2.8) вместо O (3 ** N)), которое означает, что она должна масштабироваться значительно более полого

Так, некоторые тестовые данные:

import numpy as np 

# generate test data 
def make_test_data(coeffs, mean=20.0, base=0.05): 
    w  = len(coeffs) # number of fields 
    h  = int(1.5 * w) # number of rows of data 
    rows = np.random.exponential(mean - base, (h, w)) + base 
    totals = data.dot(coeffs) 
    return rows.round(2), totals.round(2) 

, который дает нам что-то вроде

>>> rows, totals = make_test_data([0, 1, 1, 0, -1, 0.12]) 

>>> print(rows) 
[[ 1.45 17.63 22.54 5.54 37.06 1.47] 
[ 11.71 80.43 26.43 18.48 11.08 8.8 ] 
[ 16.09 11.34 63.74 3.31 13.2 13.35] 
[ 11.96 12.17 10.23 8.15 73.3 0.42] 
[ 4.03 8.01 20.84 21.46 2.76 18.98] 
[ 3.24 6.6 35.06 23.17 9.03 8.58] 
[ 25.05 33.72 6.82 0.49 46.76 12.21] 
[ 70.27 1.48 23.05 0.69 31.11 43.13] 
[ 9.04 10.45 15.08 4.32 52.94 11.13]] 

>>> print(totals) 
[ 3.29 96.84 63.48 -50.85 28.37 33.66 -4.75 -1.4 -26.07] 

и код решателя,

>>> sol = np.linalg.lstsq(rows, totals) # one line! 

>>> print(sol[0])  # note the solutions are not *exact* 
[ -1.485730e-04 1.000072e+00 9.999334e-01 -7.992023e-05 -9.999552e-01 1.203379e-01] 

>>> print(sol[0].round(3))  # but they are *very* close 
[ 0. 1. 1. 0. -1. 0.12]