Title: Use exhaustive search to solve the partition problem in C#

In the partition problem, the goal is to divide a set of numbers into two subsets that have the same total. My favorite story for the partition problem is the "booty division problem." Suppose you and a friend find a buried treasure containing crowns, necklaces, goblets, cellphones, and other goodies with different values. You want to divide the treasure into two piles of equal value, one for you and one for your friend.

This is an NP-complete problem, which means (without getting technical) that it's an extremely hard problem. Intuitively you can think of the problem as determining whether each number in the list should be placed in set 1 or set 2. There are two choices for each number and each decision is independent of the others, so to exhaustively try every possible arrangement for N numbers, you would need to examine 2^N arrangements. For example, if you found N items of treasure so N = 35, then 2^N = 34,359,738,368. If N = 40, then 2^N = 1,099,511,627,776. Even a fast computer will only be able to solve this problem for small N.

In fact, even knowing whether a list has a partition is NP-complete. Basically to discover whether you can divide the items evenly, you need to find an even division.

This example solves the partition problem by performing an exhaustive search. This is interesting by itself, but it will also help you understand future examples that:

• Use branch and bound to solve the problem more quickly
• Use the Task Parallel Library (TPL) to solve the problem on multiple threads, possibly running on different cores on your system

When you enter values in the text box on the left and click the Partition button, the button's event handler reads the values into an array of integers and calls the following PartitionValues method.

// Partition the values. Return an array with entry i = true if // value i belongs in the first set of the partition. private bool[] PartitionValues(int[] values) { // Variables to track the best solution and a test solution. bool[] best_assignment = new bool[values.Length]; bool[] test_assignment = new bool[values.Length]; // Get the total of all values. int total_value = values.Sum(); // Partition the values starting with index 0. int best_err = total_value; PartitionValuesFromIndex(values, 0, total_value, test_assignment, 0, ref best_assignment, ref best_err); // Return the result. return best_assignment; }

The PartitionValues method makes arrays to hold a test solution and the best solution found so far. An entry in one of these arrays is true if the corresponding item is assigned to set 1.

The total_value variable holds the sum of all of the items' values. The best_err value is the difference between the two sets' total values. Initially all items are in set 2 (because the boolean array entries default to false) so the initial error is the total of all of the items.

Having prepared these variables, PartitionValues calls the PartitionValuesFromIndex method (shown shortly) to recursively examine all possible divisions of the items. The parameters are:

• The values.
• The index of the first value that should be moved into one set or the other. Values with lower indexes are assumed to be fixed in a set and are not changed by later calls to PartitionValuesFromIndex.
• The sum of all of the values.
• The array holding a test assignment. Calls to PartitionValuesFromIndex will move items from set 1 to set 2 within this test assignment looking for a good solution.
• The sum of the values assigned to set 1 in the test assignment.
• The array holding the best assignment found so far.
• The error (difference in the value of the two sets) for the best assignment found so far.

The following code shows the PartitionValuesFromIndex method.

// Partition values keeping those before index start_index fixed. // test_assignment is the test assignment so far. // test_value is the total value of the first set. // Initially the best assignment and its error are in variables // best_assignment and best_err. // Update those to reflect any improved solution we find. private void PartitionValuesFromIndex(int[] values, int start_index, int total_value, bool[] test_assignment, int test_value, ref bool[] best_assignment, ref int best_err) { // If start_index is beyond the end of the array, // then all entries have been assigned. if (start_index >= values.Length) { // We're done. See if this assignment is better than // what we have so far. int test_err = Math.Abs(2 * test_value - total_value); if (test_err < best_err) { // This is an improvement. Save it. best_err = test_err; best_assignment = (bool[])test_assignment.Clone(); } } else { // Try adding values[start_index] to set 1. test_assignment[start_index] = true; PartitionValuesFromIndex(values, start_index + 1, total_value, test_assignment, test_value + values[start_index], ref best_assignment, ref best_err); // Try adding values[start_index] to set 2. test_assignment[start_index] = false; PartitionValuesFromIndex(values, start_index + 1, total_value, test_assignment, test_value, ref best_assignment, ref best_err); } }

The parameter start_index determines which value this call to the method examines. If start_index indicates a value beyond the end of the values array, then the current test solution has a complete assignment of every item to one set or another. In that case, the code calculates the error given by the test solution. This is the difference between the total values of the sets. The parameter test_value gives the total value of set 1. The value of set 2 is total_value - test_value, so the difference is:

Math.Abs(test_value - (total_value - test_value)) =
Math.Abs(2 * test_value - total_value)

If the test solution's error is smaller than the error for the best solution found so far, the program updates the best solution.

If start_index indicates a value that is inside the array, then the code tries moving that value into set 1. It sets the test_assignment value for that item to true to indicate that it is in set 1. The PartitionValuesFromIndex method then recursively calls itself to try assigning the remaining values. The new call starts from index start_index + 1 and adds the new item's value to test_value because that item is in set 1.

After it returns from the recursive call, the method tries adding the start_index item to set 2.

After the method returns from the second recursive call, the method is done. It has recursively considered all possible combinations of the items with the start_index item in set 1 or set 2.

When control returns the PartitionValues method, the best_assignment array holds the best assignment found. The button's event handler uses the array to display the results.

The number of combinations that must be examined grows exponentially with the number of items in the set, so exhaustive search only works for small problems. However, it has the benefits that it's reasonably straightforward and that it always finds the best possible solution. My next few posts will describe other approaches for solving the partition problem.

Download the example to experiment with it and to see additional details.