Partition Problem Tool
This applet can be used partition a set of integers into two subsets.
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, and then the 'BALANCE SUBSETS' 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
If you copy and paste the contents of the bottom-right text area into a spreadsheet, and sum the 2 subset columns, it will look like this:
Target Difference
When you press the 'LOAD/RELOAD SET' button the 'TARGET DIFFERENCE' text field will be set to 0 if the sum of the integers is even, or 1 if it is odd. You can change this value. Whatever value you specify, this is an exact target. If the sum of the integers is even then it should be an even number, otherwise odd. If you specify an incompatible target it will add 1 to it. The applet will strive to achieve this difference as exactly as it does 0 or 1.
This is a useful feature.
If, for instance, you wanted to partition your set 3 ways you could set the target difference to one third of the total. You'd then paste your two partitions into your spreadsheet using the two result text areas at bottom-left, and reload the larger one and partition it equally.
Or, you may have roughly balanced a large set (by some other means), having first set aside a small subset that you then balance with an offset equal to the difference.
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 1 billion. On my computer, 1 billion iterations takes around 6 minutes. 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 'BALANCE SUBSETS' 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.
Stomp
Stomp controls the extent to which the process is directed towards its goal. The default value of 50% is best for most of the time. In some quirky situations, setting it to 100% really gives it a boost, but more usually will cause it to seize up.
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 produce balanced subsets, it does not mean that it can't be done, nor will the subsets it finds necessarily be the best balanced.
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.