-1

Recently, I had to fill out a very important application form. I had to add several values together and I ended with EUR 9004.00 as a result. However, I don't find the piece of paper where I had the values written down that I actually added. I only have the total values from which I did not add all.

So I need an algorithm that takes a list of floats as input and tells me the combinations that result in EUR 9004.00. I'm not a computer scientist so I don't know if there is an algorithm that would achieve this or whether this is an incredible task (because the computer would take too long).

I'm looking for a function like this:

 def findCombinations(values:list, target_value:float) -> list):
      ...

Does an algorithm like this exist or do I have to find one myself? Also, is it reasonably possible?

David
  • 8,113
  • 2
  • 17
  • 36
phpcrack
  • 63
  • 5
  • How long is the list? – Manuel Mar 31 '21 at 08:21
  • Well, not indefinite, but 30 elements it might have. I could maybe reduce it to lets say 15 if that would be the threshold of whats possible with general computer strength. – phpcrack Mar 31 '21 at 09:37

2 Answers2

1

A possible solution will be:

  1. find the combination of the elements in the list
  2. find the sums of each combination with different length
  3. check for the sum compared to the target, this might give you more then 1 combination

Sample code will be:

from itertools import combinations as c
l = [1.1, 2.2, 3.3, 4.4, 5.5, 6.6]
target = 3.3
error_margin = 1e-4
result = [seq for i in range(len(l), 0, -1) for seq in c(l, i) if abs(sum(seq) - target) <= error_margin]

Notice that because you wish to compare floats you should allow some error margin.

You can refer to the following links:

  1. combinations
  2. compare floating points
David
  • 8,113
  • 2
  • 17
  • 36
0

Here is a generator. I use a generator because of the possibly large number of combinations of the input values that need to be checked.

import math

def powerset(s: List[int]) -> List[Tuple[int, ...]]:
    """
    Strictly the power set minus the empty set.

    powerset([1,2,3]) --> (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3) .
    """
    return (chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1)))

def findCombinations(values:list, target_value:float) -> list):
    ps = powerset(values)    # = 2**len(values) - 1 items
    for comb in ps:
        if math.isclose(sum(comb), target_value):
            yield comb

math.isclose has extra arguments so you can tune the closeness of the comparison.

Paddy3118
  • 4,704
  • 27
  • 38
  • You made a small mistake when you wrote your docstring. Your code doesn't produce the empty tuple. (It probably should, otherwise the name "powerset" is misleading.) – Manuel Mar 31 '21 at 10:12
  • Oh, yea, I removed the redundant - in this case, empty set from the powerset generator and forgot to update the docstring. I'll add a note if I can still edit. – Paddy3118 Mar 31 '21 at 18:32