Улучшение подмножества сумм - PullRequest
Новая
       24

Улучшение подмножества сумм

0 голосов
/ 06 сентября 2018

КОРОТКАЯ версия:

Есть ли способ с помощью numpy (в python) вычислить все возможные комбинации сумм из массива с плавающей точкой между двумя интервалами?

Полная (длинная) версия:

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

def subset(array, num, epsilon):
result = []
def find(arr, num, path=()):
    if not arr:
        return
    if (arr[0] >= num and arr[0] <= num + epsilon):
        result.append(path + (arr[0],))
    else:
        find(arr[1:], num - arr[0], path + (arr[0],))
        find(arr[1:], num, path)
find(array, num)
return result

def sumColumn(matrix):
    return numpy.sum(matrix, axis=1)  # axis=1 says "get the sum along the columns"


target = 7.00
suppaumaxde = 0.30

#data = [  1.98, 1.93, 1.64,  2.06, 2.18, 2.12, 3.20, 1.29, 2*0.65, 1.84*2, 1.85*2]
#, 1.58*3, 1.46*3, (1.48*3+0.22), 1.12*4, 1.85*2, 2*1.84, 2*1.84, 1.18*3, 2.38+0.02, 0.65*5,

data = [  1.13, 2.26, 3.93, 2.40-0.02, 2.38, 2.27, 1.98, 1.93, 1.64,  2.06, 2.18, 2.12, 3.20, 1.29, 2*0.65, 1.84*2,
 1.85*2, 1.58*3, 1.46*3, (1.48*3+0.22), 1.12*4, 1.85*2, 2*1.84, 1.18*3, 2.38+0.02, 0.65*5,
 3.23, 1.60, 0.58, 4.01, 1.09*3]

print data
Resultat=subset(data, target, suppaumaxde)
#print subset(data, target, suppaumaxde)
#print(' '.join(map(str, Resultat)))
#print([sum(row) for row in Resultat])
couleur='\33[37m'
print('\n')
for colonne in Resultat:
    if (sum(colonne)<=target+(suppaumaxde*1/3)):couleur='\33[42m'
    elif (sum(colonne)<=target+(suppaumaxde*2/3)):couleur='\33[43m'
    elif (sum(colonne)<=target+(suppaumaxde*3/3)):couleur='\033[91m'
    print couleur,sum(colonne),'\033[0m',(colonne)


data.sort(reverse=True)
print('\n')
print data
Resultat=subset(data, target, suppaumaxde)
#print(' '.join(map(str, Resultat)))
print('\n')
for colonne in Resultat:
    if (sum(colonne)<=target+(suppaumaxde*1/3)):couleur='\33[42m'
    elif (sum(colonne)<=target+(suppaumaxde*2/3)):couleur='\33[43m'
    elif (sum(colonne)<=target+(suppaumaxde*3/3)):couleur='\033[91m'
    print couleur,sum(colonne),'\033[0m',(colonne)


data.sort()
print('\n')
print data
Resultat=subset(data, target, suppaumaxde)
#print(' '.join(map(str, Resultat)))
print('\n')
for colonne in Resultat:
    if (sum(colonne)<=target+(suppaumaxde*1/3)):couleur='\33[42m'
    elif (sum(colonne)<=target+(suppaumaxde*2/3)):couleur='\33[43m'
    elif (sum(colonne)<=target+(suppaumaxde*3/3)):couleur='\033[91m'
    print couleur,sum(colonne),'\033[0m',(colonne)

Это начало работать, но я должен улучшить вещи:

  1. Если я упорядочу массив по-другому, я получу разные результаты. Поэтому я думаю, что некоторые результаты отсутствуют. (поэтому я повторяю код дисплея 3 раза, не выполняя функцию, чтобы показать это. Но я хочу удалить два последних)
  2. Время выполнения становится длинным, поскольку я добавляю еще несколько входных данных в массив. Может быть, это не оптимизировано и выполняет слишком много операций. Может быть, порядок перед сравнением и после достижения предельного значения перейдет к следующему пункту?
  3. В идеале мне нравилось заказывать результаты, но не добавляя слишком много времени выполнения.
  4. Какой-то результат появляется несколько раз (в качестве второго пункта я думаю, что некоторая оптимизация отсутствует)

Я только начал использовать python, так что я не понял всю программу, если вы это сделаете, я был бы рад улучшить это с вашим советом:)

Этим утром я тоже публикую это на Reddit, а Laserdude10642 расскажет о numpy, Итак, после запуска RTFM, кажется, это хороший вариант, чтобы быть более эффективным, я немного попробовал, найдя другие примеры: 

import numpy as np

def find_nearest(array, value):
array = np.asarray(array)
idx = (np.abs(array - value)).argmin()
return array[idx]


montab = [  2.95, 2.26, 3.93, 2.38*2, 1.98, 1.93, 1.64, 0.53, 1.20, 2.06, 2.18, 2.12, 3.20, 1.29, 1.20, 2*0.65, 1.84*2,
 1.85*2, 1.58*3, 1.46*3, (1.48*3+0.22), 1.12*4, 1.18*3, 2.38+0.02, 0.65*5,
 3.23, 1.60, 0.58, 4.01, 1.09*3, 0.60]

cible= 7

print(find_nearest(montab, cible))

Но мне нужно отобразить все результаты, которые находятся в асимметричном интервале

Есть ли способ с помощью numpy вычислить все возможные комбинации сумм между двумя интервалами?

PS1: извините за мой плохой английский: /

PS2: в идеале мне нравится, чтобы код оставался более понятным, чтобы потом его было легче модифицировать

PS3: я запускаю свою программу на python внутри Geany (на Linux Mint), команда execute - "python"% f ", есть ли простой способ запустить его на нескольких ядрах, чтобы он работал быстрее? (Без адаптации программы для нескольких -thread?)

PS4: Невозможно начать вопрос с «Привет» или «Привет»? Я пробовал оба, но исчезает каждый раз.

1 Ответ

0 голосов
/ 06 сентября 2018

Я нашел другое решение, но все еще не хорошее решение, основанное на этом другом вопросе stackoverflow : 

from numpy import *
from itertools import *

montab = [  2.95, 2.26, 3.93, 2.38*2, 1.98, 1.93, 1.64, 0.53, 1.20, 2.06, 2.18, 2.12, 3.20, 1.29, 1.20, 2*0.65, 1.84*2,
 1.85*2, 1.58*3, 1.46*3, (1.48*3+0.22), 1.12*4, 1.18*3, 2.38+0.02, 0.65*5,
 3.23, 1.60, 0.58, 4.01, 1.09*3, 0.60, 0, 0]

target=7
suppaumaxde = 0.35


print montab
montab.sort(reverse=True)
print montab
couleur='\33[37m'
print('\n')
for colonne in combinations(montab,4):
    if (sum(colonne)>=target and sum(colonne)<=target+suppaumaxde):
        if (sum(colonne)<=target+(suppaumaxde*1/3)):couleur='\33[42m'
        elif (sum(colonne)<=target+(suppaumaxde*2/3)):couleur='\33[43m'
        elif (sum(colonne)<=target+(suppaumaxde*3/3)):couleur='\033[91m'
        print couleur,sum(colonne),'\033[0m',(colonne)

Но результат не очень хороший, и его нужно улучшить / найти другое решение:

  1. Я должен установить количество элементов и добавить нули в массив данных
  2. Все комбинации проверены, это большая потеря
  3. Результат не отсортирован
...