How to divide an array into 3 parts with the sum of each part roughly equal

13,148

Solution 1

The original poster already has a working solution (noted in comments) to split the array into two parts with equal sums; call this split2. The three-part version can be constructed using split2.

  1. Add to the array a new number equal to one-third of the sum of the original numbers.
  2. Split the array into two parts using split2.
  3. One part has the number that was added; remove it.
  4. Split the other part into two using split2.

Solution 2

This is like two-Partition problem which is NP-Hard but not in strong sense, you can have an O(nK) algorithm for it where K is size of your input sum, See pseudo polynomial time algorithm for subset sum, Also See my answer for divide-list-in-two-parts-that-their-sum-closest-to-each-other, but in your case you should just add another dimension to process it.

Solution 3

Try the following code

int total = 0, partSum = 0, partIndex = 0;
int noOfParts = 3; //Initialize the no. of parts
int[] input = { 10, 8, 8, 7, 6, 6, 6, 5 };
int[] result = new int[noOfParts]; //Initialize result array with no. of locations equal to no. of parts, to store partSums
foreach (int i in input) //Calculate the total of input array values
{
    total += i;
}
int threshold = (total / noOfParts) - (total / input.Length) / 2; //Calculate a minimum threshold value for partSum
for (int j = input.Length - 1; j > -1; j--)
{
    partSum += input[j]; //Add array values to partSum incrementally
    if (partSum >= threshold) //If partSum reaches the threshold value, add it to result[] and reset partSum  
    {
        result[partIndex] = partSum;
        partIndex += 1;
        partSum = 0;
        continue;
    }
}
if (partIndex < noOfParts) //If no. of parts in result[] is less than the no. of parts required, add the remaining partSum value
{
    result[partIndex] = partSum;
}
Array.Reverse(result);
foreach (int k in result)
{
    Console.WriteLine(k);
}
Console.Read();     

I've tested this with various values in array(arranged in descending order) and also with different value for no. of parts(3,4,5...) and got good results.

Solution 4

// calculate total
total = 0;
for(i = 0; i != size; ++i) {
   total += array[i];
}

// partition
n_partitions = 3;
current_partition = 1;
subtotal = array[0];
for(i = 1; i != size; ++i) {
   if(subtotal + array[i] > total / n_partitions) {
      // start new partition;
      current_partition++;
      subtotal = array[i];
   } else {
      // push to current partition
      subtotal += array[i];
   }
}
Share:
13,148

Related videos on Youtube

hienvd
Author by

hienvd

Full snack developer

Updated on June 04, 2022

Comments

  • hienvd
    hienvd almost 2 years

    I have an arranged array and I want to divide it into 3 parts so that their sum are closest to each other.

    Ex: I have this array:
    
        10, 8, 8, 7, 6, 6, 6, 5
    
    so it'll be divided into 3 part like:
    
        p1 {10,8} sum = 18
        p2 {8,7,6} sum = 21
        p3 {6,6,5} sum = 17
    
    
  • culithay
    culithay over 12 years
    I see my sample is bad. It's too long =))
  • hienvd
    hienvd over 12 years
    Why we have this code? int threshold = (total / parts)-(total / array.Length) / 2;
  • culithay
    culithay over 12 years
    @vuonghien: Congratulation you have solved your problem. Why don't you vote for the attendees ^^. Long source code....
  • HitOdessit
    HitOdessit about 9 years
    Nice algorithm, but there is a problem with it in case when totalSum of all elements in source array equals to zero. In this case split2 function call make no sense, since it'll split exactly all original array and new "fake" element.
  • Michael J. Barber
    Michael J. Barber about 9 years
    @Hit Interesting point. In practice, the case when totalSum is zero is trivial: you have the original set and two empty sets. Depending on how split2 works, this trivial solution might not be obtained, though, if the approach I described is followed blindly.