Не знаете, как интегрировать функцию отрицательного числа в алгоритм генерации данных? - PullRequest
Новая
       22

Не знаете, как интегрировать функцию отрицательного числа в алгоритм генерации данных?

2 голосов
/ 11 февраля 2012

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

Я думаю, что я могу решить эту проблему - поставить ошейник на возможные результаты, чтобы предотвратить бесконечность результатов (если яблоки равны 2, а апельсины равны -1, тогда для любой суммы будут бесконечные решения, но если я скажем, что есть предел тому, что он не может продолжаться вечно.)

Итак, вот супер базовый код, который определяет вес: 

import math

data = [-2, 10,5,50,20,25,40]
target_sum = 100
max_percent = .8 #no value can exceed 80% of total(this is to prevent infinite solutions

for node in data:
    max_value = abs(math.floor((target_sum * max_percent)/node))
    print node, "'s max value is ", max_value

Вот код, который генерирует результаты (первая функция генерирует таблицу, если это возможно, а вторая функция составляет фактические результаты. Подробности / псевдокод алгоритма здесь: Можно ли масштабировать алгоритмы перебора? ): 

from collections import defaultdict

data = [-2, 10,5,50,20,25,40]
target_sum = 100
# T[x, i] is True if 'x' can be solved
# by a linear combination of data[:i+1]
T = defaultdict(bool)           # all values are False by default
T[0, 0] = True                # base case


for i, x in enumerate(data):    # i is index, x is data[i]
    for s in range(target_sum + 1): #set the range of one higher than sum to include sum itself
        for c in range(s / x + 1):  
            if T[s - c * x, i]:
                T[s, i+1] = True

coeff = [0]*len(data)
def RecursivelyListAllThatWork(k, sum): # Using last k variables, make sum
    # /* Base case: If we've assigned all the variables correctly, list this
    # * solution.
    # */
    if k == 0:
        # print what we have so far
        print(' + '.join("%2s*%s" % t for t in zip(coeff, data)))
        return
    x_k = data[k-1]
    # /* Recursive step: Try all coefficients, but only if they work. */
    for c in range(sum // x_k + 1):
       if T[sum - c * x_k, k - 1]:
           # mark the coefficient of x_k to be c
           coeff[k-1] = c
           RecursivelyListAllThatWork(k - 1, sum - c * x_k)
           # unmark the coefficient of x_k
           coeff[k-1] = 0

RecursivelyListAllThatWork(len(data), target_sum)

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

Заранее спасибо, и если что-то неясно, пожалуйста, дайте мне знать.

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

1 Ответ

4 голосов
/ 12 февраля 2012

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

for c in range(s / x + 1):

на 

max_value = int(abs((target_sum * max_percent)/x))
for c in range(max_value + 1):

Это гарантирует, что любой коэффициент в конечном ответе будет целым числом в диапазонеОт 0 до max_value включительно.

Простой способ добавления отрицательных значений - изменить цикл по s с 

for s in range(target_sum + 1):

на 

R=200 # Maximum size of any partial sum
for s in range(-R,R+1):

Обратите внимание, что если вы делаетеТаким образом, ваше решение будет иметь дополнительные ограничения.Новое ограничение заключается в том, что абсолютное значение каждой частичной взвешенной суммы должно быть <= R. </p>

(Вы можете сделать R большим, чтобы избежать этого ограничения, уменьшая количество решений, но это замедлит выполнение.)

Полный код выглядит так: 

from collections import defaultdict

data = [-2,10,5,50,20,25,40]

target_sum = 100
# T[x, i] is True if 'x' can be solved
# by a linear combination of data[:i+1]
T = defaultdict(bool)           # all values are False by default
T[0, 0] = True                # base case

R=200 # Maximum size of any partial sum
max_percent=0.8 # Maximum weight of any term

for i, x in enumerate(data):    # i is index, x is data[i]
    for s in range(-R,R+1): #set the range of one higher than sum to include sum itself
        max_value = int(abs((target_sum * max_percent)/x))
        for c in range(max_value + 1):  
            if T[s - c * x, i]:
                T[s, i+1] = True

coeff = [0]*len(data)
def RecursivelyListAllThatWork(k, sum): # Using last k variables, make sum
    # /* Base case: If we've assigned all the variables correctly, list this
    # * solution.
    # */
    if k == 0:
        # print what we have so far
        print(' + '.join("%2s*%s" % t for t in zip(coeff, data)))
        return
    x_k = data[k-1]
    # /* Recursive step: Try all coefficients, but only if they work. */
    max_value = int(abs((target_sum * max_percent)/x_k))
    for c in range(max_value + 1):
       if T[sum - c * x_k, k - 1]:
           # mark the coefficient of x_k to be c
           coeff[k-1] = c
           RecursivelyListAllThatWork(k - 1, sum - c * x_k)
           # unmark the coefficient of x_k
           coeff[k-1] = 0

RecursivelyListAllThatWork(len(data), target_sum)
...