Best practices

I have a list which consists of numeric values.

In Python, it is written as:

[959, 3480, 9346, 8367, 2847, 8330, 6946, 9586, 9722, 2775]

Or in the case of MySQL:

create table testtb(n int);
insert into testtb values(959),(3480),(9346),(8367),(2847),(8330),(6946),(9586),(9722),(2775);

I would like to find the elements with a sum value of 43219 from the list.

I believed SQL might not be the best choice so I chose programming and finished it.

Here is how I did it in Python using the following script:

import random
ls=[959, 3480, 9346, 8367, 2847, 8330, 6946, 9586, 9722, 2775]
length=len(ls)

flag=True
while flag:
  new_ls=random.sample(ls,length) #get a list with the same elements but in different order
  print(f'\n\na new list with the following combination begins: {new_ls}')
  total=0
  index=0
  for n in new_ls:
    total=total+n
    if total>43219:  #there is no need to keep on using the current list
      break
    elif total==43219:  #found the answer
      print(f'\nfound the combination:{new_ls[:index+1]}')
      print(f'it has a length of {index+1}')
      print(f'the sorted list is:{sorted(new_ls[:index+1])}')
      flag=False
      break
    index+=1

After running the script, I got the answer after some failed combinations:

a new list with the following combination begins: [8330, 9346, 8367, 9722, 959, 9586, 2847, 3480, 6946, 2775]


a new list with the following combination begins: [6946, 2847, 2775, 959, 8367, 8330, 3480, 9346, 9586, 9722]


a new list with the following combination begins: [2775, 3480, 959, 8367, 9586, 9722, 8330, 6946, 9346, 2847]

found the combination:[2775, 3480, 959, 8367, 9586, 9722, 8330]
it has a length of 7
the sorted list is:[959, 2775, 3480, 8330, 8367, 9586, 9722]

Of course, the similar could be done in MySQL. A temporary table can be created using:

select n from testtb order by rand();

Then use a cursor to get the value from each row and add them one by one. And compare the sum to the constant value.

Either way, the problem is that the resolution depends on too much randomness. Is there some better way to achieve this in Python or MySQL?

Improve this question

6 Replies 6

matszwecja
•

For each element in a list, you can either take it for the sum or not. Write a recursive function with a (list, sum) as parameters and do two recursive calls after removing first element from the list. In one call you take the element for the sum (thus subtracting it from the sum needed), in other you don't take it (sum stays the same). If sum gets <0, you can stop checking on that branch. If sum == 0, you have found your answer.

That method is called Dynamic Programming, and is a common approach to Subset sum problem

Improve this answer
Suleman Elahi
•

You can generate list of all possible combinations from using itertools.combinations()

Then check if sum of all those combinations will match the constat value that you have.

I don't know how efficient you want it to be but it surely is a one way to do it.

Example generating combinations: https://stackoverflow.com/a/56397669/25131836

Improve this answer
Akina
•

If your values list is always tiny then you may use the next query:

create table test (n int);
insert into test values(959),(3480),(9346),(8367),(2847),(8330),(6946),(9586),(9722),(2775);
SELECT * FROM test;

SET @sum = 43219;

WITH RECURSIVE
cte1 (id, n) AS (
  SELECT ROW_NUMBER() OVER (ORDER BY n DESC),
         n
  FROM test
  ), 
cte2 (id, id_list, cur_sum) AS (
  SELECT id, CAST(id AS CHAR(1024)), n
  FROM cte1
  WHERE n <= @sum
  UNION ALL
  SELECT cte1.id, CONCAT_WS(',', cte2.id_list, cte1.id), cte2.cur_sum + cte1.n
  FROM cte2 
  JOIN cte1 ON cte1.id > cte2.id
  WHERE cte2.cur_sum + cte1.n <= @sum
  ),
cte3 (combination, id_list) AS (
  SELECT ROW_NUMBER() OVER (), id_list
  FROM cte2
  WHERE cte2.cur_sum = @sum
  ),
cte4 (combination, n) AS (
  SELECT cte3.combination, cte1.n
  FROM cte3
  CROSS JOIN JSON_TABLE(CONCAT('[', cte3.id_list, ']'),
                        '$[*]' COLUMNS (id INT PATH '$')) jsontable
  JOIN cte1 ON jsontable.id = cte1.id
  )
SELECT * FROM cte4
combination n
1 9722
1 9586
1 8367
1 8330
1 3480
1 2775
1 959

fiddle

Your 10 values in the values list produces the generation of ~ 900 combinations, and the amount will grow exponentially.

CAUTION!!! If the values list will have more than ~20 values then your server may hang!

Improve this answer
Reinderien
•

This is a straightforward assignment problem. I don't trust that recursion or itertools will be efficient. I suggest trying a linear programming solver:

import numpy as np
from scipy.optimize import milp, Bounds, LinearConstraint

ls = np.array((959, 3480, 9346, 8367, 2847, 8330, 6946, 9586, 9722, 2775))
total = 43219

result = milp(
    c=np.zeros_like(ls), integrality=True, bounds=Bounds(lb=0, ub=1),
    constraints=LinearConstraint(A=ls, lb=total, ub=total),
)
assert result.success, result.message
print(ls[result.x > 0.5])
Improve this answer
blabla_bingo
•

Thank you all for your suggestions. After making a list out of 500 numbers ranged from 1 to 1 million and got a sum from 365 randomly selected numbers, I did some test to achieve the sum. Although all of the solutions can accomplish the task, performance wise I suppose SQL is not really cut out for this job. I have yet to try iteration and recursion. But at the moment I find the linear programming solution provided by @Reinderien is quite efficient. Tests are done using my not-so-good test environment virtual machine.

Here is the list of 500 elements I generated in case you are interested:

[158064, 985173, 866810, 525006, 690969, 709510, 90690, 989695, 395345, 540401, 599863, 646950, 423384, 817808, 852300, 119192, 44103, 812018, 514515, 88894, 33349, 794618, 198589, 514645, 230954, 96944, 163188, 14773, 847924, 255805, 754686, 797482, 989919, 79978, 796982, 832532, 134368, 903780, 135028, 266141, 675359, 163792, 754189, 883119, 175486, 419498, 524097, 888139, 445601, 776101, 986632, 886060, 767468, 435055, 484290, 174887, 854845, 847567, 275211, 615904, 536531, 952129, 964204, 560219, 421609, 177278, 372366, 420748, 996244, 166647, 966431, 698478, 620662, 243220, 178082, 687068, 447403, 928702, 270539, 194888, 2856, 795681, 98686, 778584, 642784, 446541, 122613, 202380, 636374, 28124, 593570, 76898, 484269, 989717, 368638, 107331, 703946, 526966, 59067, 574700, 145598, 647011, 501892, 600193, 179516, 404691, 982806, 433543, 476888, 267051, 535029, 782981, 993654, 603745, 895112, 671999, 556776, 571724, 147061, 157072, 797304, 218485, 58093, 377261, 44105, 214318, 917284, 579593, 378908, 229597, 110984, 604974, 816335, 938025, 598083, 391382, 830643, 456021, 443172, 351259, 430547, 328720, 289295, 949156, 116931, 438188, 819790, 443836, 178184, 193009, 796502, 499009, 756343, 187876, 357347, 198956, 658144, 774011, 890540, 502728, 691185, 647791, 584242, 803287, 838973, 446096, 219128, 983242, 434560, 260073, 495654, 602907, 386595, 465366, 760351, 830919, 604790, 33217, 35479, 839925, 975955, 868107, 555672, 246526, 689304, 912681, 615764, 737615, 415436, 929203, 785666, 929208, 342436, 141094, 955059, 31425, 326629, 701076, 603294, 149953, 928821, 204922, 479677, 51163, 995878, 414710, 879341, 948129, 540728, 787550, 643593, 978004, 920736, 91696, 395594, 148351, 808395, 119172, 597875, 469080, 659812, 448862, 610804, 837080, 906579, 682975, 215794, 455430, 411720, 886825, 424740, 151631, 883567, 148307, 805459, 781419, 574772, 289921, 981646, 254777, 332364, 753705, 491612, 145607, 613994, 201351, 269091, 864742, 10224, 666813, 786661, 448059, 392639, 90136, 269083, 162287, 776926, 966626, 548748, 668813, 787679, 127378, 616980, 13335, 128404, 387530, 325369, 632880, 695649, 38473, 851333, 650296, 931723, 272435, 500652, 58977, 149482, 465770, 337542, 7028, 129062, 30657, 131185, 865550, 101586, 198601, 44983, 210649, 656983, 989202, 754947, 114396, 893563, 76676, 228110, 360328, 426998, 908817, 928651, 284524, 656863, 498983, 764346, 843111, 823411, 781434, 871232, 150364, 665312, 53563, 88649, 651117, 727838, 602696, 380859, 879579, 468671, 831772, 36165, 360985, 515170, 809589, 531336, 399891, 31271, 525256, 267863, 871524, 150305, 326007, 475656, 904358, 30417, 831495, 224590, 755982, 914818, 134589, 416869, 904217, 931694, 599565, 957230, 273573, 828729, 390006, 898117, 749741, 672765, 879644, 578261, 248621, 226161, 562201, 6170, 91167, 377749, 524991, 938366, 949183, 604806, 677365, 749543, 424063, 844271, 564501, 816849, 978508, 254424, 85610, 429226, 621539, 443375, 601916, 36563, 147253, 101197, 674990, 475239, 936892, 446483, 232022, 840428, 215632, 697623, 827998, 731621, 437513, 911744, 278020, 278755, 941551, 893492, 314778, 731518, 524896, 530606, 838442, 467091, 471271, 74543, 102461, 190427, 14989, 50025, 433361, 22648, 509831, 450729, 202155, 136406, 347522, 24611, 304564, 741520, 905682, 650058, 979672, 337075, 684624, 848947, 556091, 486267, 42946, 949930, 97795, 213636, 28876, 145939, 227234, 494397, 16058, 94530, 195712, 545925, 615578, 740414, 196950, 680200, 146937, 877526, 876627, 694489, 63920, 802010, 156188, 661968, 412927, 81880, 108639, 894949, 633552, 681039, 50129, 317246, 231930, 185702, 534232, 120321, 883257, 316256, 68931, 429077, 765544, 641722, 321672, 199992, 835702, 176090, 435716, 840319, 335819, 39976, 13865, 997044, 786014, 248881, 922334, 698015, 523649, 843196, 800903, 757294, 314681, 13200, 213705, 902029, 216962, 467897, 453070, 150638, 393930, 465727, 244872, 196418, 962457, 371369, 548184, 562217, 403401]

goal=183725561
Improve this answer
Kenny Ostrom
•

as an addendum to what @matszwecja said, perform your exact match test against a set of existing sums, as in the "two sum" problem. If the numbers are always positive, you can prune any results greater than {target}-{minimum}

Improve this answer

Your Reply

By clicking “Post Your Reply”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.