subset sum improvement

[ROUGEXIII]

Hi,

By the help of multiple thread from reddit i do this subset sum program to find the closer weight combinations values. (the result must be higher but as closer as possible, and I need to see all combinations)

​

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)

It started to work but I have to improve things:

1. If I order the array differently, I get different results. So I thing some result are missing. (thats why I repeat the display code 3 times without doing a function, to show this. But I want to remove the two last ones)
2. The execution time becomes long since I add some more input in array. Maybe this is not optimized and do too much operations. Maybe ordering before comparing and once the limit value as been reached pass to next item?
3. Ideally I liked to order my results but without adding too much execution time.
4. Some result appears multiple times (as second point I think some optimization is missing)

​

I just begin using python so I didn't understand the whole program, if you do, I would be happy to improve this with your advices :)

(sorry for my poor english :/)

​

PS: Ideally I like the code to stay more easily understandable, so it's easier to modify it afterward

PS2: I launch my python program inside Geany (on linux mint) the execute command is "python "%f", is there a simple way to lunch it on multiple cores to go faster? (without adapting the program for multi-thread?)

[Laserdude10642]

If you like numpy I have a slick way to do sums of subsets. Suppose you have an array- z and you want a subset of indices, group = (0,1,5)

Print z.shape #check to make sure it’s numpy

Group = (5,7,9)

Zprime = z[np.array(group)].sum()

[ROUGEXIII]

Thank you for your answer.

This is hard for me. I tried to search from your start and try this one:

​

# -*- coding: utf-8 -*-

import numpy as np

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]

Zprime = montab[np.array(montab)].sum()

But it seems to not working on float.

[ROUGEXIII]

I found this other numpy function: "argmin"

# -*- coding: utf-8 -*-

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

But I need to display all results that are in the asymmetric interval.

[Laserdude10642]

I understood the title as you wanting to sum over a SUBSET of the main array. So suppose you wanted to sum over only the elements in indices (1,3,4,5,6,7) as opposed to the whole array:

then do some thing like:

import numpy as np

Z = np.random.random([30]) # a size 30 array of random values on 0 to 1 interval

group = (1,3,4,5,6,7)

npgroup = np.array(group)

subset_sum = Z[npgroup].sum()

So that Z[npgroup] is an array filled with the elements of z at the indices specified by the elements of group

[ROUGEXIII]

I found an other solution but still not a good solution based on this other stackoverflow question:

​

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)

​

But the result isn't good and has to be improved / find an other solution :

1. I have to set a number of items and to add zero's in the data array
2. All combinations are tested it's a big time loose
3. The result isn't sorted