Sumedh Meshram

.Net Technical Blog

The Partition Problem - Algorithm [Solved]

Partition Problem Problem

Partition problem is the task of deciding whether a given multiset of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the elements in S1 equals the sum of the elements in S2.

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);
            }
        }
}

Add comment

  Country flag

biuquote
  • Comment
  • Preview
Loading