All possible combinations of numbers with rounding error matching sum

user_14833143 0
Viewed 63

I have encountered one problem that I struggle to solve. There is a group of numbers that should match some given sum and the function should output all possible combinations. The length of the input numbers differ, might be 3 or sometimes 20 numbers in the input array. Unfortunately, some numbers do have a rounding error and some do not have it, and we do not know which ones are accurate. Therefore, not always combination might be found for every sum, cause of it rounding error.

E.g. there are numbers 248, 512, 992, 240, 2134, 4214, 4211 and target sum is 3133.

I wanted to incorporate rounding error into the function that I found here:

## Create algorithm to find out underlying accounts
def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
        
    if partial_sum >= target:
        return
    
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

And i wanted to do so by sort of extending the input array by 2*len(input_array) elements, where one would be an element-1 and second would be element+1.

Unfortunately, I do not know how to incorporate it into that algorithm and when i use loop to run the function multiple times with switching one element it will be super slow and create 3*length runs of this functions(actual number, actual number-1, actual numer+1). I dont think anyone would be able to help with this...

algorithm python
1 Answers

Ok, I guess you're looking for the "best" sum, rather than "exact" one, that is, find a subset sum such as the distance abs(partial_sum, target) is minimal. You can employ this simple modification of the algorithm: on each step, compute the distance and declare it "best" if it is less than the best distance so far.

Here's some working code (I also replaced recursion with a loop and a queue):

def best_subset_sum(lst, target):
    ## queue of candidates: (indexes, partial sum)
    queue = [([i], lst[i]) for i in range(len(lst))]

    ## best candidate so far: (indexes, distance to target)
    best = [[], target]

    while queue:
        indexes, s = queue.pop(0)

        ## the distance between the current sum and the target
        diff = abs(target - s)

        ## is it better than the shortest so far?
        if diff < best[1]:
            ## new best distance
            best = indexes, diff
            ## exact sum found - stop now
            if diff == 0:
                break

        ## assuming all numbers are positive
        if s < target:
            i = indexes[-1] + 1
            ## for all indexes following the current combination
            while i < len(lst):
                ## add current combination + i-th element to the queue
                queue.append((indexes + [i], s + lst[i]))
                i += 1

    return [lst[i] for i in best[0]]

s = best_subset_sum([248, 512, 992, 240, 2132, 4214, 4211], 3133)
print(s, sum(s))

This prints

[248, 512, 240, 2134] 3134

And here's a modification to enumerate all such sums:

def best_subset_sums(lst, target):
    queue = [[[i], lst[i]] for i in range(len(lst))]
    best = [[[], target]]

    while queue:
        indexes, s = queue.pop(0)

        diff = abs(target - s)

        if diff < best[0][1]:
            best = [[indexes, diff]]
        elif diff == best[0][1]:
            best.append([indexes, diff])

        if s < target:
            i = indexes[-1] + 1
            while i < len(lst):
                queue.append((indexes + [i], s + lst[i]))
                i += 1

    for b in best:
        yield [lst[i] for i in b[0]]


for ls in best_subset_sums([3, 5, 7, 11, 13, 17, 19], 66):
    print(ls, sum(ls))

# [5, 11, 13, 17, 19] 65
# [7, 11, 13, 17, 19] 67
user_9891210
Related