Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
3  
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

3 Answers 3

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.

share|improve this answer
    
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.

share|improve this answer
2  
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);
        }
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.