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.

Use branch and bound to solve the partitioning problem more quickly than an exhaustive search in C#See Solve the partitioning problem by using an exhaustive search in C# for a description of the partitioning problem and an explanation of how you can solve it using an exhaustive search. Branch and bound is a technique for reducing the number of branches you need to visit while searching a tree. You can consider the partitioning problem as a tree search if you consider each decision whether to put an item in set 1 or set 2 as selecting a branch in the tree. If there are N items, then the tree is a full binary tree …

Use branch and bound with an initial heuristic to solve the partitioning problem in C#See Use branch and bound to solve the partitioning problem more quickly than an exhaustive search in C# for information about using branch and bound to solve partitioning problem. Branch and bound avoids visiting branches in a search tree if that branch cannot possibly improve the best solution found so far. However, the initial implementation of branch and bound begins by recursively always assigning items to set 1. That means the first solution the program considers places every item in set 1 and that’s a pretty terrible solution. That means the program doesn’t have a tight bound on …

Pingback: Use branch and bound to solve the partitioning problem in C# - C# HelperC# Helper

Pingback: Use branch and bound to solve the partitioning problem in C#C# Helper