Find all numbers that sum closest to a given number python

Question

I have a script below that gives the closest 2 values to a given sum. It also iterates through a list of given sums and after each iteration removes the numbers that have already been used.

I need to modify this script so that it produces a necessary amount of values closest to each sum, rather than 2. The script needs to accept float values and cannot re-use values. Effectively it needs to pick the most efficient set closest to target, update the set to remove values used, then move on to next target etc..

With pairs it it doesn't work very well for specific use cases/sets that require 3 numbers or 4 etc. to actually get closest to the sum. I need this script to also be able to accept float values, which this script currently does.

Any suggestions would be much appreciated. Also if someone knows a better script for this, please let me know.

import sys
def find_closese_sum(numbers, target):
    start = 0
    end = len(numbers) - 1
    result = sys.maxint
    result_tuple = None
    while start < end:
        if numbers[start] + numbers[end] == target:
            print 0, (numbers[start], numbers[end])
            return
        elif numbers[start] + numbers[end] > target:
            if abs(numbers[start] + numbers[end] - target) < result:
                result = abs(numbers[start] + numbers[end] - target)
                result_tuple = (numbers[start], numbers[end])
            end -= 1
        else:
            if abs(numbers[start] + numbers[end] - target) < result:
                result = abs(numbers[start] + numbers[end] - target)
                result_tuple = (numbers[start], numbers[end])
            start += 1

    for i in result_tuple:
        numbers.remove(i)

    return result_tuple

if __name__ == "__main__":
    target = [14,27,39]
    numbers = [1,5,5,10,7,8,11,13,66,34]
    print numbers
    numbers = sorted(numbers)


    for i in target:
        result_shown = find_closese_sum(numbers, i)

        print result_shown

Answer 1

I don't see any elegant way to do this, so you probably are going to have to brute force the solution. Make all possible subsets of numbers, sum them, and check which is the closest to the target. It would look something like this.

from itertools import permutations

def find_closest_sum(numbers, target, n):
    permlist = list(permutations(numbers, n))
    sumlist = [sum(l) for l in permlist]
    maxpos = 0
    for i in range(1, len(sumlist)):
        if abs(sumlist[i] - target) < abs(sumlist[maxpos]-target):
             maxpos = i

     return permlist[maxpos]

numbers = [1,5,5,10,7,8,11,13,66,34]
result_shown = find_closest_sum(numbers, 20, 4)
print result_shown

Using permutations makes a lot of the code you wrote unnecessary.

Answer 2

My answer, using python 3 but you should be able to port it easily.

from itertools import combinations as c

if __name__ == "__main__":
    target = [14,27,39]
    numbers = [1,5,5,10,7,8,11,13,66,34]

    for combo in range(1,4):
        for i in target:
            #lambda to find the difference between sum and target
            diff = lambda x: abs(sum(x) - i)
            #get all unique combinations
            combos = {tuple(sorted(c)) for c in c(numbers, combo)}
            #sort them
            combos = sorted(combos, key = diff)
            #get the smallest difference
            smallest = diff(combos[0])
            #filter out combos larger than the smaller difference
            result = [c for c in combos if diff(c) == smallest]
            print('results for {}, best combinations are off by {}:'.format(i, smallest))
            print(result)

You stated you need to exclude numbers used for a previous result. To do that just remove them from the list:

            #after print(result), inside the "for i in target" loop
            #if you want to exclude all numbers used in all combinations
            numbers = [n for n in numbers if n not in [b for a in result for b in a]]
            #if you only need to remove the first match
            numbers = [n for n in numbers if n not in result[0]]

Answer 3

import numpy as np
import itertools

def find_closese_sum(numbers, targets):
    numbers = numbers[:]
    for t in targets:
        if not numbers:
            break
        combs = sum([list(itertools.combinations(numbers, r))
                     for r in range(1, len(numbers)+1)], [])
        sums = np.asarray(list(map(sum, combs)))
        bestcomb = combs[np.argmin(np.abs(np.asarray(sums) - t))]
        numbers = list(set(numbers).difference(bestcomb))
        print("Target: {},  combination: {}".format(t, bestcomb))

Example

In [101]: import numpy as np
     ...: import itertools
     ...: 
     ...: def find_closese_sum(numbers, targets):
     ...:     numbers = numbers[:]
     ...:     for t in targets:
     ...:         if not numbers:
     ...:             break
     ...:         combs = sum([list(itertools.combinations(numbers, r))
     ...:                      for r in range(1, len(numbers)+1)], [])
     ...:         sums = np.asarray(list(map(sum, combs)))
     ...:         bestcomb = combs[np.argmin(np.abs(np.asarray(sums) - t))]
     ...:         numbers = list(set(numbers).difference(bestcomb))
     ...:         print("Target: {},  combination: {}".format(t, bestcomb))
     ...: 
     ...: targets = [14,27.,39]
     ...: numbers = [1.0,5,5,10,7,8,11,13,66,34]
     ...: find_closese_sum(numbers, targets)
     ...: 
Target: 14,  combination: (1.0, 13)
Target: 27.0,  combination: (5, 5, 10, 7)
Target: 39,  combination: (8, 34)

Answer 4

Without making it complex here is my approach, Try this :

import itertools
def finding_closet(ls,target,depth):
    closest = []
    for i in itertools.combinations(ls, depth):

        if sum(i) == target:
            return i
        else:
            closest.append((abs(sum(i) - target), i))
    return min(closest)[1]

Test_case 0:

print(finding_closet([1,5,5,10,7,8,11,13,66,34],20,2))

output:

(7, 13)

Test_case 1:

print(finding_closet([1,5,5,10,7,8,11,13,66,34],20,4))

output:

(1, 5, 5, 8)

test_case_3:

print(finding_closet([1,5,5,10,7,8,11,13,66,34],20,8))

output:

(1, 5, 5, 10, 7, 8, 11, 13)