|
Subset Sum Tool This applet can be used obtain a subset that sums to specified value from a set of integers. The set can contain up to 10,000 positive integers. The integers can sum up to 999,999,999,999,999,999. It's easy to use. You'll find detailed instructions further down. Putting it briefly, you just paste (or type) your set of integers (with or without associated identifiers) into the input text area, press a couple of buttons, and copy the resultant subsets from the output text area. It uses the CSV (comma seperated values) import/export format used by most spreadsheets. |
|
Here's a example of input (it includes some invalid lines). If you want to give the applet a quick whirl, copy and paste it into the text area at the top, press the 'LOAD/RELOAD SET' button, change the Target Subset Sum to 3000000, and then press the 'OBTAIN SUBSET' button. The result will appear in the text areas at the bottom.
123456,"item 01" 789012,item 2 111111, 222222 121212,24 345,track 14 2468,length side a 1066, and all that 543219,circuit A104 784304, POMEGRANATES 986543 ,integer missing 109o46 4587*5,invalid integer 486720 666777 999999 060644 856200.edge 81 737022,area45 64084,crate 12112 784,3 x 4 length 784 666 1492 Or, here's another set to play around with, that's bit closer to my heart...jazz tracks with playing time in seconds. Try setting the subset sum to something like 2760, and see what you get.
333,Bill Evans: Loose Bloose 125,Paul Barbarin: Slide Frog Slide 261,Paul Barbarin: Give It Up 447,Freddie Hubbard: Caravan 946,John Coltrane: India 361,Bill Evans: Time Remembered 323,Bill Evans - Loose Blues: My Bells 380,Art Farmer Quartet: Some Time Ago 441,Jimmy Smith: Beggar For The Blues 348,Jimmy Smith: Walk On The Wild Side 438,Art Farmer Quartet: Embraceable You 403,Art Farmer Quartet: Days Of Wine And Roses 257,Wayne Shorter: Wayning Moments 207,Woody Herman: Sister Sadie 346,Lennie Tristano: C Minor Complex 382,Dexter Gordon: Soy Califa 316,Benny Goodman: Titter Pipes 389,Freddie Hubbard: I'll Never Smile Again 317,Bill Evans and Jim Hall: Skating In Central Park 257,John Coltrane: Say It 168,John Coltrane: It's Easy To Remember 190,John Coltrane: Nancy 764,Miles Davis: The Time Of The Barracudas 363,Miles Davis: Summer Night 819,Cannonball Adderley Sextet: Intro/Gemini 420,Cannonball Adderley Sextet: Dizzy's Business 354,Cannonball Adderley Sextet: Scotch And Water 194,Thelonius Monk: Five Spot Blues 251,John Coltrane: In A Sentimental Mood 250,Duke Ellington: Caravan 442,Wes Montgomery: Born To Be Blue 581,Wes Montgomery: Cariba 196,Bud Powell at the Golden Circle: Star Eyes 916,Bud Powell at the Golden Circle: Blues In The Closet 490,Bud Powell at the Golden Circle: Like Someone In Love 293,Chico Hamilton: One For Joan 487,Chico Hamilton: Freedom Traveller 258,Miles Davis: Aos Pes Da Cruz 326,Charlie Ventura and Gene Krupa: Perdido 742,Dizzy Gillespie: The Empire 228,Count Basie: I'm Shoutin' Again 307,MJQ: Piazza Navona 267,Jan Johansson: Visa Fraan Utanmyra 263,Erroll Garner: Mack The Knife 505,Jackie McLean: Omega 607,Freddie Hubbard: Summertime Target Subset Sum When you first press the 'LOAD/RELOAD SET' button, the 'TARGET SUBSET SUM' text field will be set to zero. Set it to whatever value you want. It will stay at that value until you change it. Subset Details This text field contains details of the subset that sums to the value that you've specified. If you cut and paste it into a spreadsheet you can verify the result. Residual Set Details The residual set contains the members that were not included in the subset. If you repeatedly copy and paste this text area over the original input set, load it, and obtain a further subset, you have the basis of a bin packing tool. Max.Iterations The maximum number of iterations is calculated according to the size of the loaded set. This is the number of combinations it randomly works through before giving up. It won't set a value higher than 100 million. On my computer, 100 million iterations takes less than a minute. You can change the value to any value between 10 billion and zero. If the target has not been achieved by the time the maximum number of iterations is reached, it presents the best result that it has been able to achieve in the time. If you then press 'OBTAIN SUBSET' it will carry on from where it left off. By adusting the number of iterations, you are 'time boxing' the process, and raising or lowering the expectation of accuracy. DISCLAIMER: As with all the tools on these pages, if you are using them for some serious purpose, it is up to you to check the result. You can use a spreadsheet to easily check that the selected integers add up correctly. You should also check that all your input has been accepted, and correctly interpreted. Also, it needs to be understood that, if the applet fails to find the correctly summing subset, it does not mean that there is none, nor will the subset it finds necessarily be the closest. Generated Input Data If you don't have any real data to put into the applet. you can use the applet below to list random numbers that you can copy and paste. It will generate up to 10,000 numbers within the range that you set. |