The resultant partition: two balanced subsets of the original set

Directly partition your set by checking all possible permutations. This method is best used on small sets where the solution must be accurate.

bruteForce [ 1, 1, 1, 1, 1, 1, 6 ] == ( [ 1, 1, 1, 1, 1, 1 ], [ 6 ] )

A <greedy> method would distribute some ones into the second subset in the above example, but bruteForce will obtain the optimal solution.

Since all possible partitons must be calculated, this is an O(2ᴺ) operation.

bruteForce (List.range 0 22)

Emits a heap limit allocation failure and sets with smaller lengths take some time to compute. So alternate methods are best once your sets get large.

Traverse the list once i.e. O(N), chosing to place the current value into the sublist that minimises the objective at the current point in time.

The greedy method is fast and can handle large lists, but can be quite inaccurate. Let's take a look at few examples:

greedy [ 22, 5, 15, 3, 9, 12, 7, 11, 5, 2 ] == ( [ 11, 12, 3, 15, 5 ], [ 2, 5, 7, 9, 22 ] )


bruteForce [ 22, 5, 15, 3, 9, 12, 7, 11, 5, 2 ] == ( [ 22, 5, 15, 3 ], [ 9, 12, 7, 11, 5, 2 ] )

Both of these partitions have values of 1, meaning both partitions are equivalent and equally valid.

As your lists get larger the performance of the greedy solution becomes obvious. The method has issues handling lists of length 23, whereas greedy handles them near instantaneously.

greedy (List.range 0 22) ( [ 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2 ], [ 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1, 0 ] )

In fact, List.range 0 500000 is really no problem.

The downfall of this method occurs when lists are weighted in such a manner that seems fine initially (to the algorithm), but is toppled at the end of the list.

greedy [ 1, 1, 1, 1, 1, 1, 6 ] == ( [ 1, 1, 1 ], [ 6, 1, 1, 1 ] )

Generates all possible partitions of a given set of numbers.

allPartitions [ 3, 15 ] == [ ( [ 3, 15 ], [] ), ( [ 3 ], [ 15 ] ), ( [ 15 ], [ 3 ] ), ( [], [ 3, 15 ] ) ]

Note that this function scales as O(2ᴺ), where N is the length of your list.

The objective for our partitioning is to minimise the difference between the sum of each subset. Mathematically stated: min |∑S₁-∑S₂| : S₁,S₂⊂S.

objective ( [ 22, 5, 15, 3 ], [ 9, 12, 7, 11, 5, 2 ] ) == 1


objective ( [ 7, 3, 2 ], [ 22, 5, 15, 9, 12, 11, 5 ] ) == 67

These examples are partitions from the same set. The first is a far better solution than the second.

Outputs the sum of each subset to validate the quality of a partition.

sumOfSets ( [ 22, 5, 15, 3 ], [ 9, 12, 7, 11, 5, 2 ] ) == ( 45, 46 )