Partitioning set into subsets with respect to equality of sum among subsets

Let's say I have `{3, 1, 1, 2, 2, 1, 5, 2, 7}` set of numbers, I need to split the numbers such that sum of subset1 should be equal to sum of subset2 `{3,2,7} {1,1,2,1,5,2}`. First we should identify whether we can split number(one way might be dividable by 2 without any remainder) and if we can, we should write our algorithm two create s1 and s2 out of s.

How to proceed with this approach? I read partition problem in wiki and even in some articles but I am not able to get anything. Can someone help me to find the right algorithm and its explanation in simple English?

-
You'll get a Nobel Prize (Turing Award) if you solve this for "any" set of numbers. If I'm right, this is Number Partitioning and is NP-Complete :) –  PhD Jun 16 '12 at 18:57
This is not an easy problem. Look into "linear programming" or/and "constraint programming". With regards to the letter: I think this problem could be relatively easily modelled in Mozart/Oz. –  wmeyer Jun 16 '12 at 19:03

As @wmeyer noticed, this problem can be stated quite nicely using Constraint Programming. And this simple problem instance is easily solved.

First, here is a high level model written in MiniZinc which is basically this code, without the output section. (See http://www.hakank.org/minizinc/partition_into_subset_of_equal_values.mzn for the full model.)

```% problem instance and its length
array[1..n] of int: s = [3, 1, 1, 2, 2, 1, 5, 2, 7];
int: n = 9;

% number of subsets
int: num_subsets = 2;

% the decision variables
% to which subset does x[i] belong?
array[1..n] of var 1..num_subsets: x;

solve satisfy; % we want all solutions

% Constraints

% Ensure that the sum of the subsets are the same
constraint
forall(p in 1..num_subsets-1) (
sum([s[i]*bool2int(x[i] == p) | i in 1..n]) ==
sum([s[i]*bool2int(x[i] == p+1) | i in 1..n])
)
;

% symmetry breaking: assign the first number to subset 1
constraint x[1] = 1;

```

Since the question is tagged "C#", here's model using the C# interface of Google or-tools (with a little different approach than the MiniZinc model): http://www.hakank.org/google_or_tools/partition_into_subsets_of_equal_values.cs

Note: For the given numbers - and using the symmetry breaking of assigning the first number to subset 1 - there are 19 different partitions (solutions) with 2 subsets, and 42 different partitions when using 3 subsets. For 4 subset there is no solution.

-
Some more about performance: I've tested the MiniZinc model with 100 and 1000 random integers in the range 1..10 (1..100): the first solution is shown in a few milliseconds. For 10000 random integers (in the range 1..10) then it took a little bit longer: about 3 seconds after about 20 seconds of generating the intermediate FlatZinc format. This variant is here: hakank.org/minizinc/partition_into_subset_of_equal_values2.mzn (it's 28kB). –  hakank Jun 17 '12 at 18:32
And this C# version (hakank.org/or-tools/partition_into_subsets_of_equal_values2.cs) solves the problem with 100000 random integers (in the ranges of 1..10, 1..100 as well as 1..1000) in about 3 seconds. –  hakank Jun 17 '12 at 19:10

As somebody commented, this problem is isomorphic to “subset sum”, and so it’s NP-complete. Basically, the naive solutions to this problem are the best solutions and they’re very, very bad. :) I only say this so you don’t look for a more “optimized” version or something.

-
In general, this is an NP-complete problem. For small-ish integers it is solvable by dynamic programming in time that is polynomial in the sum of the inputs. –  kevin cline Jun 17 '12 at 17:37
``````using System;
using System.Linq;
public class CandidateCode
{
public static string partition(int[] input1)
{
bool[] best_assignment = PartitionValues(input1);

string result1 = "", result2 = "";
int total1 = 0, total2 = 0;
for (int i = 0; i < best_assignment.Length; i++)
{
if (best_assignment[i])
{
result1 += "\r\n " + input1[i];
total1 += input1[i];
}
else
{
result2 += "\r\n " + input1[i];
total2 += input1[i];
}
}
if (result1.Length > 0) result1 = result1.Substring(2);
if (result2.Length > 0) result2 = result2.Substring(2);

return "{"+ result1 + " } {" + result2 + " } total  " + total1.ToString() + " & " + total2.ToString();
}

private static bool[] PartitionValues(int[] values)
{
bool[] best_assignment = new bool[values.Length];
bool[] test_assignment = new bool[values.Length];

int total_value = values.Sum();

int best_err = total_value;
PartitionValuesFromIndex(values, 0, total_value, test_assignment, 0, ref best_assignment, ref best_err);

return best_assignment;
}

private static 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);
}
}
}
``````
-