Sunday, August 3, 2014

Partition an array of integers into sub-arrays so that the difference of summaries (of sub-arrays) is minimal


Here is one solution (dynamic programming) for partition an array of integers into two sub-arrays so that the difference of summaries (of sub-arrays) is minimal.
// partition an array of integers into two sub-arrays so that the difference of summaries (of sub-arrays) is minimal
int balancePartitionTwoWays(int arr[], int n, int partition[2]) {

 if (n==2) {
  for (int i=0; i<2; i++) {
   partition[i]=arr[i];
  }
  return abs(partition[0]-partition[1]);
 }


 // loop through the array to find out the sum and maximum
 int sum=0;
 int maximum = -1;
 for(int i=0; i<n; i++){
  sum += arr[i];
  if (arr[i]>maximum) maximum = arr[i];
 }

 // allocate the matrix to remember
 bool memo[sum+maximum+1][2];
 for (int j = 0; j < 2; j++)
  for (int i = 0; i <= sum+maximum; i++)
    memo[i][j] = false;

 memo[0][0] = true;

 // mark memo[i][k] to true if there is a subset
    // of array [0..i-1] with sum equal to i
 for (int j = 0; j < n; j++) {
  for (int i = 0; i <= sum+maximum; i++) {

   if (memo[i][j%2]) {
    memo[i][(j+1)%2] = true;
    memo[i+ arr[j]][(j+1)%2] = true;

   }
  }
 }

 int max_diff = INT_MAX;
 int part[2];

 for (int i = 0; i <= sum+maximum; i++) {
  if (memo[i][n % 2]) {
   part[0]=i;
   part[1]=sum-i;
   int temp = abs(part[0]-part[1]) ;
   if (temp<max_diff) {
    max_diff = temp;
    partition[0] = part[0];
    partition[1] = part[1];
   }
  }
 }

 return max_diff;

}



// partition an array of integers into three sub-arrays so that the difference of summaries (of sub-arrays) is minimal
int balancePartitionThreeWays(int arr[], int n, int partition[3]) {

 if (n==3) {
  for (int i=0; i<3; i++) {
   partition[i]=arr[i];
  }
  return abs(partition[0]-partition[1]) + abs(partition[1]-partition[2]) + + abs(partition[2]-partition[0]);
 }


 // loop through the array to find out the sum and maximum
 int sum=0;
 int maximum = -1;
 for(int i =0; i<n; i++){
  sum += arr[i];
  if (arr[i]>maximum) maximum = arr[i];
 }

 // allocate the matrix to remember
 bool memo[sum+maximum+1][sum+maximum+1][2];
 for (int k = 0; k < 2; k++)
  for (int i = 0; i <= sum+maximum; i++)
   for (int j = 0; j <= sum+maximum; j++)
    memo[i][j][k] = false;

 memo[0][0][0] = true;

 // mark memo[i][j][k] to true if there is a subset
    // of array [0..i-1] with sum equal to i
 for (int k = 0; k < n; k++) {
  for (int i = 0; i <= sum+maximum; i++) {
   for (int j = 0; j <= sum+maximum; j++) {
    if (memo[i][j][k%2]) {
     memo[i][j][(k+1)%2] = true;
     memo[i+ arr[k]][j][(k+1)%2] = true;
     memo[i][j+ arr[k]][(k+1)%2] = true;
    }
   }
  }
 }

 int max_diff = INT_MAX;
 int part[3];

 for (int i = 0; i <= sum+maximum; i++) {
  for (int j = 0; j <= sum+maximum; j++) {

   if (memo[i][j][n % 2]) {
    part[0]=i;
    part[1]=j;
    part[2]=sum-i-j;

    //int temp = abs(part[0]-part[1]) + abs(part[1]-part[2]) + + abs(part[2]-part[0]);
    int temp = 0;
    for (int k=0; k<3; k++) {
     temp += abs(part[k%3]-part[(k+1)%3]);
    }
    if (temp<max_diff) {
     max_diff = temp;
     for (int k=0; k<3; k++) {
      partition[k]=part[k];
     }
    }
   }
  }
 }

 return max_diff;

}



Enjoy the journey. 

3 comments:

  1. I must thank you for the efforts you have put in penning this site. I am hoping to check out the same high-grade content by you later on as well. In truth, your creative writing abilities has inspired me to get my own, personal blog now..

    Linux Training in Chennai

    ReplyDelete
  2. This blog is having the general information. Got a creative work and this is very different one.We have to develop our creativity mind.This blog helps for this. Thank you for this blog. This is very interesting and useful.

    ccna training in chennai thiruvanmiyur

    ReplyDelete
  3. This is an awesome post.Really very informative and creative contents. These concept is a good way to enhance the knowledge.I like it and help me to development very well.Thank you for this brief explanation and very nice information.Well, got a good knowledge.

    PPC Services in Chennai

    ReplyDelete