ISourceCode

Make the frequent cases fast and the rare case correct

Balanced Partition Problem – Finding the minimized sum between two partitions of a set of positive integers

In Balanced Partition problem,you have a set of n integers each in the range 0 … K. Partition these integers into two subsets such that you minimize |S1 – S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.

A dynamic programming solution to this problem is provided in this video tutorial by Brian C. Dean. It is problem number 7.

The Balanced Partition problem is a variation of the Partitioning problem Which is NP complete. In partitioning problem the objective is to decide whether a given multiset of integers can be partitioned into two “halves” that have the same sum.

There are many ways to solve this problem.

One approach was the way of doing a differencing heuristic similar to what Kamarkar-karp did to solve the partition problem. The Analysis of Kamarkar-Karp can be found at the link.The differencing algorithm at each step removes two numbers from the set and replaces them by their difference.

To get a detail understanding of this problem and why the Kamarkar-Karp approach is not suitable for all cases is described here by American Scientist article by Brian Hayes

Stephan Mertens in this paper describes a optimized algorithm that combines the balanced largest differencing method (BLDM) and Korf’s complete Karmarkar-Karp algorithm.

Algorithm:
Firstly this algorithm can be viewed as knapsack problem where individual array elements are the weights and half the sum as total weight of the knapsack.

1.take a solution array as boolean array sol[] of size sum/2+1

2. For each array element,traverse the array and set sol [j] to be true if sol [j - value of array] is true

3.Let halfsumcloser be the closest reachable number to half the sum and partition are sum-halfsumcloser and halfsumcloser.

4.start from halfsum and decrease halfsumcloser once everytime until you find that sol[halfsumcloser] is true

import java.io.*;
import java.util.*;
 
public class balpart 
{
	public static void main (String [] args) throws IOException 
	{
        
		int sum = 0;
		System.out.println("Enter the number of array elements");
		Scanner input = new Scanner(System.in);
		int N = input.nextInt();
		int[] array = new int[N];
		System.out.println("Enter the Positive elements of the array");
		for(int member = 0; member < N ; member++)
		{
			array[member] = input.nextInt();
			sum += array[member];		
		}
      
             	boolean [] sol = new boolean [sum / 2 + 1];
        
        	sol [0] = true;//empty array
        	for (int i : array) 
		{
        		for (int j = sum / 2; j >= i; j--) 
			{
                		if (sol [j - i]) 
				sol [j] = true;
            		}
        	}
                     
        	int halfsumcloser = sum / 2;
        	for (; !sol [halfsumcloser]; halfsumcloser--);
		System.out.println ("The Minimum sum After partioning the array is :" +((sum - halfsumcloser) - halfsumcloser));
         
    	}
}

OUTPUT:

labuser@ubuntu:~$ java balpart
Enter the number of array elements
10
Enter the Positive elements of the array
2 10 3 8 5 7 9 5 3 2
The Minimum sum After partioning the array is :0

labuser@ubuntu:~$ java balpart
Enter the number of array elements
2
Enter the Positive elements of the array
1
5
The Minimum sum After partioning the array is :4

There are further question that we can pose here.

A). In the easiest hard problem article author states that for input
2 10 3 8 5 7 9 5 3 2

there are 23 ways to divide up the numbers into two groups with exactly equal sums
one such partition is [2 5 3 10 7] [2 5 3 9 8]

So can we integrate into this algorithm a method to find the total different ways to make a balanced partition.

B) Can we find the exact partition elements?

The above algorithm takes lot of time on huge numbers resulting in large sums.So again we end up with a not so good algorithm.

One Related article i have already written is Algorithm to implement “Equal Sum Subsets” – For a sequence of numbers, find a subset[s](same order as original sequence) in which each subset has the same smallest sum

That’s it for now. I hope to present more articles on partition problem and its variants

Thanks for Reading !

About these ads

6 responses to “Balanced Partition Problem – Finding the minimized sum between two partitions of a set of positive integers

  1. Hudson March 22, 2011 at 4:12 am

    What about “minimize |S2 – 2*S1|” partition problem?

  2. James Kevin D. Quimbo April 13, 2012 at 4:00 am

    Ah Sir can you pls solve this problem pls!
    How much space does 2 HDD partitions need from a 500 gigabyte HDD to create a balance HDD!
    Thanks!

  3. Caroline July 11, 2012 at 7:54 pm

    Que fórmula você usou para saber que existem 23 maneiras de dividir os números em dois grupos??

  4. Caroline July 11, 2012 at 7:56 pm

    What formula you used to know that there are 23 ways to divide the numbers into two groups?

  5. Ayodeji April 22, 2013 at 11:54 am

    It could be solve as such too

    public class Partition {

    static int[] arr = {2, 10, 3, 8, 5, 7, 9, 5, 3, 2};//{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    static int[] pat;
    static int right;
    static int left = 0;
    static int sumLeft, sumRight;
    static int j, k;

    static public void main(String[] args) {
    Arrays.sort(arr);

    right = arr.length – 1;
    pat = new int[arr.length];

    if (arr.length % 2 == 0) {
    calcEven();
    } else {
    calcOdd();
    }
    sumUpPartion();
    System.out.println(“Left Partition: ” + sumLeft + “\nRight Partition: ” + sumRight);
    System.out.println(“Minimum diff: ” + Math.abs(sumLeft – sumRight));

    }

    static void calcEven() {
    for (int i = 0; i < arr.length; i += 2) {
    j = arr[i];
    k = arr[i + 1];
    sumUpPartion();
    if (sumLeft <= sumRight) {
    pat[left++] = Math.max(j, k);
    pat[right--] = Math.min(j, j);
    } else {
    pat[left++] = Math.min(j, k);
    pat[right--] = Math.max(j, k);
    }
    }
    }

    static void calcOdd() {
    int temp = arr[0];
    arr[0] = arr[arr.length - 1];
    arr[arr.length - 1] = temp;
    for (int i = 0; i < arr.length – 1; i += 2) {
    j = arr[i];
    k = arr[i + 1];
    sumUpPartion();
    if (sumLeft sumRight) {
    pat[right--] = arr[arr.length - 1];
    } else {
    pat[left++] = arr[arr.length - 1];
    }

    }

    static void sumUpPartion() {
    sumLeft = 0;
    sumRight = 0;
    int i, n;

    int m = pat.length / 2;
    if (arr.length % 2 == 0) {
    for (i = 0, n = m; i < m || n < pat.length – 1; i++, n++) {
    sumLeft += pat[i];
    sumRight += pat[n];
    }
    } else {
    for (i = 0, n = m; i < m || n < pat.length; i++, n++) {
    //System.out.println(i + " " + j);
    sumLeft += pat[i];
    sumRight += pat[n];
    }
    }
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: