Find set of numbers in a list that together add up to X

Question

Find set of numbers in a list that together add up to X

Asked 6 years, 10 months ago

Viewed 111 times

0

I need to do a program where I have a list of numbers (1571.48 | 327.53 | 286.60 | 349.50 | 517.67 | 247.00 | 882.73 | 274.00 | 237.50 | 301.00 | 973.50 | 288.75 | 347.50 | 326.81) And I need to find in the middle of that list numbers that don’t repeat each other and that together add up to 4600.31 or 2331.26. I did it this way, but it will take forever to find the right combination.

vetor = [1571.48, 327.53, 286.60,349.50,517.67,247.00,882.73,274.00,237.50,301.00,973.50,288.75,347.50,326.81]
for a in range(0,13):
    for b in range(0,13):
        if vetor[a] + vetor[b] == 2331.26 or vetor[a] + vetor[b] == 4600.31:
            print ("%s + %s = %s" % (vetor[a], vetor[b], vetor[a] + vetor[b]))
        for c in range(0,13):
            if vetor[a] + vetor[b] + vetor[c] == 2331.26 or vetor[a] + vetor[b] + vetor[c] == 4600.31:
                print ("%s + %s + %s = %s" % (vetor[a], vetor[b], vetor[c], vetor[a] + vetor[b] + vetor[c]))
            for d in range(0,13):
                if vetor[a] + vetor[b] + vetor[c] + vetor[d] == 2331.26 or vetor[a] + vetor[b] + vetor[c] + vetor[d] == 4600.31:
                    print ("%s + %s + %s + %s = %s" % (vetor[a], vetor[b], vetor[c], vetor[d], vetor[a] + vetor[b] + vetor[c] + vetor[d]))
                for e in range(0,13):
                    if vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] == 2331.26 or vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] == 4600.31:
                        print ("%s + %s + %s + %s + %s = %s" % (vetor[a], vetor[b], vetor[c], vetor[d],vetor[e], vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e]))
                    for f in range(0,13):
                        if vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] == 2331.26 or vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] == 4600.31:
                            print ("%s + %s + %s + %s + %s + %s = %s" % (vetor[a], vetor[b], vetor[c], vetor[d], vetor[e], vetor[f], vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f]))
                        for g in range(0,13):
                            if vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] == 2331.26 or vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] == 4600.31:
                                print ("%s + %s + %s + %s + %s + %s + %s = %s" % (vetor[a], vetor[b], vetor[c], vetor[d], vetor[e], vetor[f], vetor[g], vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g]))
                            for h in range(0,13):
                                if vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] == 2331.26 or vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] == 4600.31:
                                    print ("%s + %s + %s + %s + %s + %s + %s + %s = %s" % (vetor[a], vetor[b], vetor[c], vetor[d], vetor[e], vetor[f], vetor[g], vetor[h], vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h]))
                                for i in range(0,13):
                                    if vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] == 2331.26 or vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] == 4600.31:
                                        print ("%s + %s + %s + %s + %s + %s + %s + %s + %s = %s" % (vetor[a], vetor[b], vetor[c], vetor[d], vetor[e], vetor[f], vetor[g], vetor[h],vetor[i],vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i]))
                                    for j in range(0,13):
                                        if vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] + vetor[j] == 2331.26 or vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] + vetor[j] == 4600.31:
                                            print ("%s + %s + %s + %s + %s + %s + %s + %s + %s + %s = %s" % (vetor[a], vetor[b], vetor[c], vetor[d], vetor[e], vetor[f], vetor[g],vetor[h], vetor[i],vetor[j],vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] + vetor[j]))
                                        for k in range(0,13):
                                            if vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] + vetor[j] + vetor[k] == 2331.26 or vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] + vetor[j] + vetor[k] == 4600.31:
                                                print ("%s + %s + %s + %s + %s + %s + %s + %s + %s + %s + %s" % (vetor[a], vetor[b], vetor[c], vetor[d], vetor[e], vetor[f], vetor[g],vetor[h], vetor[i], vetor[j],vetor[k]))
                                            for l in range(0,13):
                                                if vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] + vetor[j] + vetor[k] == 2331.26 or vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] + vetor[j] + vetor[k] + vetor[l] == 4600.31:
                                                    print ("%s + %s + %s + %s + %s + %s + %s + %s + %s + %s + %s + %s" % (vetor[a], vetor[b], vetor[c], vetor[d], vetor[e], vetor[f],vetor[g], vetor[h], vetor[i], vetor[j], vetor[k], vetor[l]))
                                                for m in range(0,13):
                                                    if vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] + vetor[j] + vetor[k] + vetor[m] == 2331.26 or vetor[a] + vetor[b] + vetor[c] + vetor[d] +vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] + vetor[j] + vetor[k] + vetor[l] + vetor[m] == 4600.31:
                                                        print ("%s + %s + %s + %s + %s + %s + %s + %s + %s + %s + %s + %s + %s" % (vetor[a], vetor[b], vetor[c], vetor[d], vetor[e], vetor[f],vetor[g], vetor[h], vetor[i], vetor[j], vetor[k], vetor[l], vetor[m]))
                                                    for n in range(0,13):
                                                        if vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] + vetor[j] + vetor[k] + vetor[m] + vetor[n] == 2331.26 or vetor[a] + vetor[b] + vetor[c] + vetor[d] + vetor[e] + vetor[f] + vetor[g] + vetor[h] + vetor[i] + vetor[j] + vetor[k] + vetor[m] + vetor[n] == 4600.31:
                                                            print ("%s + %s + %s + %s + %s + %s + %s + %s + %s + %s + %s + %s + %s + %s" % (vetor[a], vetor[b], vetor[c], vetor[d], vetor[e], vetor[f], vetor[g], vetor[h], vetor[i], vetor[j],vetor[k], vetor[l], vetor[m], vetor[n]))

Someone would have a shape tip or even library for me to be able to optimize the program, because I believe it will take longer than days.

1

It was not very clear the problem. Can you explain better the part of numbers that repeat and that add up to 4600.31 or 2331.26? If possible, give an example of what those numbers would be in the list.

– Woss

2017/11/22 at 10:12
1

A tip: if you have 2 levels of loop nesting think if you can’t improve. If you have 3 or 4 chances of having something wrong there. If you have five or more, I’d say you’re wrong even if you have to. It is not a question of library, it is a question of solving the problem in another way, but it is not clear what you want. This seems to be a case we can make with for and maybe it has how to optimize to become a more complex.

– Maniero

2017/11/22 at 10:27
@Andersoncarloswoss the list of numbers is 327.53 | 286.60 | 349.50 | 517.67 | 247.00 | 882.73 | 274.00 | 237.50 | 301.00 | 973.50 | 288.75 | 347.50 | 326.81

– Hebert

2017/11/22 at 21:28
@Hebert, yes, the list is the only thing that was clear in the question; what is unclear is what he meant by "repeating numbers" and "adding up to 4600.31 or 2331.26". Explain these parts and give examples what would be the desired exit.

– Woss

2017/11/22 at 21:40
@Andersoncarloswoss For example: I have a list of numbers: (25, 35, 60, 75, 90) and the result of the sum needs to be: 135, so the program will make several attempts until it will arrive on the 60+75 attempt, and it will result 135, and then the program will print the numbers that were used to make the sum and the final result. Only instead of (25, 35, 60, 75, 90) is the list I gave you, and instead of the final result being 135 is 4600.31 or 2331.26, now understood?

– Hebert

2017/11/22 at 22:00
And "numbers that do not repeat each other" would mean that the 60+60 combination was not considered, even if it resulted in the desired value?

– Woss

2017/11/22 at 22:02
I implemented the logic and none of the combinations of values in the list present in the question results in a sum equal to one of the expected values. Is that right? Any of the combinations should result in this sum?

– Woss

2017/11/22 at 22:09
Yes, 60+60 could not appear as well as 25 + 25 + 60 or 60 + 75 + 90 + 90 could not be considered either, by my mistake I forgot a number in the original list which is 1571.48, and it was expected that some combination would result 4600.31 or 2331.26, recalling that it could be a sum of 2 (327.53 + 286.60) numbers or a sum of 5 (327.53 + 286.60 + 349.50 + 517.67 + 247.00)

– Hebert

2017/11/23 at 00:06

Show 3 more comments

1 answer

Browser other questions tagged python python-3.x

You are not signed in. Login or sign up in order to post.

by Woss • **73,416** points · Answer 1 · 2017-11-23T00:35:39+00:00

The module itertools has the function combinations, which generates a certain combination from the elements of an eternal object. That is, when we do combinations('stack', 3), we will have all combinations 3 to 3 of the letters that make up the word "stack".

As the number of elements in the combination must change, that is, combine 1 to 1, then 2 to 2, then 3 to 3, etc., we must generate all possible combinations from 1 to the length of the initial list.

We do it this way:

from itertools import combinations

numbers = [1571.48, 327.53, 286.60, 349.50, 517.67, 247.00, 882.73, 274.00, 237.50, 301.00, 973.50, 288.75, 347.50, 326.81]

for i in range(len(numbers)):
    for combination in combinations(numbers, i):
        if sum(combination) in {4600.31, 2331.26}:
            print('A soma de ', combination, 'resultou em', sum(combination))

^{See working on Ideone | Repl.it}

That is, we generate all possible combinations and if the sum of this combination is 4600.31 or 2331.26, we display a message. If you run this code, the result will be that no combination has such sum. This is because we are working with floating point numbers, so we cannot compare the equality of two values; there is always the possibility of some rounding error due to the representation of the value in memory and it may be that the sum, instead of giving exactly the value, get very close.

The easiest way around this would be to define a possible deviation from the value; something like: if the sum of the values in the combination subtracted from the desired value is less than 1, then we can consider that the sum was the desired value. In code, it would look like this:

from itertools import combinations

numbers = [1571.48, 327.53, 286.60, 349.50, 517.67, 247.00, 882.73, 274.00, 237.50, 301.00, 973.50, 288.75, 347.50, 326.81]

for i in range(len(numbers)):
    for combination in combinations(numbers, i):
        s = sum(combination)
        if abs(s - 4600.31) < 1 or abs(s - 2331.26) < 1:
            print('A soma de ', combination, 'resultou em', s)

^{See working on Ideone | Repl.it}

The result of this code is:

A soma de  (1571.48, 327.53, 517.67, 882.73, 973.5, 326.81) resultou em 4599.72
A soma de  (327.53, 286.6, 349.5, 247.0, 882.73, 237.5) resultou em 2330.86
A soma de  (327.53, 247.0, 882.73, 237.5, 288.75, 347.5) resultou em 2331.01
A soma de  (286.6, 349.5, 882.73, 274.0, 237.5, 301.0) resultou em 2331.33
A soma de  (247.0, 882.73, 237.5, 288.75, 347.5, 326.81) resultou em 2330.29
A soma de  (882.73, 274.0, 237.5, 301.0, 288.75, 347.5) resultou em 2331.48
A soma de  (1571.48, 286.6, 349.5, 247.0, 882.73, 973.5, 288.75) resultou em 4599.5599999999995
A soma de  (1571.48, 286.6, 882.73, 237.5, 301.0, 973.5, 347.5) resultou em 4600.3099999999995
A soma de  (327.53, 349.5, 517.67, 247.0, 274.0, 288.75, 326.81) resultou em 2331.2599999999998
A soma de  (327.53, 517.67, 274.0, 237.5, 301.0, 347.5, 326.81) resultou em 2332.0099999999998
A soma de  (1571.48, 327.53, 286.6, 349.5, 517.67, 247.0, 973.5, 326.81) resultou em 4600.090000000001
A soma de  (1571.48, 327.53, 286.6, 349.5, 517.67, 274.0, 301.0, 973.5) resultou em 4601.280000000001
A soma de  (1571.48, 327.53, 517.67, 247.0, 973.5, 288.75, 347.5, 326.81) resultou em 4600.240000000001
A soma de  (1571.48, 286.6, 349.5, 517.67, 274.0, 301.0, 973.5, 326.81) resultou em 4600.56
A soma de  (1571.48, 517.67, 274.0, 301.0, 973.5, 288.75, 347.5, 326.81) resultou em 4600.71
A soma de  (286.6, 349.5, 247.0, 274.0, 237.5, 301.0, 288.75, 347.5) resultou em 2331.85

Note that no sum resulted exactly in the expected values, but arrived very close.

Read more on Inaccurate result in broken numbers calculation