Find set of numbers in a list that together add X

Question

Find set of numbers in a list that together add X

Navigation

#1 by (1 votes)

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 this list numbers that do not repeat each other and together add 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 hint of form or even a library for me to optimize the program, as I believe it will take more than days to do so.

python python-3.x

asked by anonymous 22.11.2017 / 06:49

1 answer

Force open .EML file in email client I can not get an Array

score 1 · Accepted Answer

The itertools module has the combinations function, which generates a particular combination from the elements of an iterable object. That is, by doing combinations('stack', 3) , we will have all combinations 3 to 3 of the letters that form 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. p>

We do this 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 at 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 a sum. This is because we are working with floating-point numbers, so we can not 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, rather than giving exactly the value, comes very close.

The easiest way around this would be to define a possible value deviation; something like: if the sum of the values in the subtracted combination of the desired value is less than 1, then we can assume that the sum was the desired value. In code, this 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 at 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

Notice that no sum has resulted exactly in expected values, but has come very close.

Read more in Inaccurate result in calculation with broken numbers