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
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.
split2. split2. 
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.
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.
// 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];
}
}
Updated with code:
The approach I suggest is as follows (with code below):
With the above logic, you will always be adding to the output part with the lowest overall value (which will help to keep the parts of similar overall value).
(in the code sample below I have skipped the array sorting step as your example is already sorted)
Code:
// the input array
int[] inputArray = new int[] { 10, 8, 8, 7, 6, 6, 6, 5 };
// the number of parts you want
int numberOfOutputParts = 3;
// create the part structures
List<Part> listOfParts = new List<Part>();
for(int i =0; i < numberOfOutputParts; i++)
{
listOfParts.Add(new Part());
}
// iterate through each input value
foreach (int value in inputArray)
{
// find the part with the lowest sum
int? lowestSumFoundSoFar = null;
Part lowestValuePartSoFar = null;
foreach(Part partToCheck in listOfParts)
{
if (lowestSumFoundSoFar == null || partToCheck.CurrentSum < lowestSumFoundSoFar)
{
lowestSumFoundSoFar = partToCheck.CurrentSum;
lowestValuePartSoFar = partToCheck;
}
}
// add the value to that Part
lowestValuePartSoFar.AddValue(value);
}
The code for the Part class used above (although you could use something better is as follows):
public class Part
{
public List<int> Values
{
get;
set;
}
public int CurrentSum
{
get;
set;
}
/// <summary>
/// Default Constructpr
/// </summary>
public Part()
{
Values = new List<int>();
}
public void AddValue(int value)
{
Values.Add(value);
CurrentSum += value;
}
}
Could you try my sample, this may help you
My Algorithm: 1/ Calculate avg value of the array numbers by the number of output array (exp:value=3 in your post)
2/ Sum the array numbers until the Sum has min gap compare to the avg value (calculated in 1/)
3/ Do step 2 until you go to the end of the array numbers
I using C# 3.5 to test
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;
namespace WindowsFormsApplication2
{
public partial class Form2 : Form
{
public Form2()
{
InitializeComponent();
}
ArrayList inputValue = new ArrayList();
int avgValue = 0;
bool isFinish = false;
private void button1_Click(object sender, EventArgs e)
{
#region Init data
isFinish = false;
avgValue = 0;
inputValue.Clear();
listBox1.Items.Clear();
//assum you input valid number without space and in desc sorting order
string[] arrNumber = textBox1.Text.Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries);
int numberOfBreak = 3;
int record = Convert.ToInt32(arrNumber[0]);//update the record with the maximum value of the array numbers
for (int i = 0; i < arrNumber.Length; i++)
{
inputValue.Add(Convert.ToInt32(arrNumber[i]));
}
foreach (object obj in inputValue)
{
avgValue += (int)obj;
}
avgValue = avgValue / numberOfBreak;
#endregion
int lastIndex = 0;
while (!isFinish)
{
int index = GetIndex(lastIndex);
string sResult = "";
for (int i = lastIndex; i <= index; i++)
{
sResult += inputValue[i].ToString() + "-";
}
listBox1.Items.Add(sResult);
if (index + 1 < inputValue.Count)
{
lastIndex = index + 1;
}
sResult = "";
}
}
private int GetIndex(int startIndex)
{
int index = -1;
int gap1 = Math.Abs(avgValue - (int)inputValue[startIndex]);
int tempSum = (int)inputValue[startIndex];
if (startIndex < inputValue.Count - 1)
{
int gap2 = 0;
while (gap1 > gap2 && !isFinish)
{
for (int i = startIndex + 1; i < inputValue.Count; i++)
{
tempSum += (int)inputValue[i];
gap2 = Math.Abs(avgValue - tempSum);
if (gap2 <= gap1)
{
gap1 = gap2;
gap2 = 0;
index = i;
if (startIndex <= inputValue.Count - 1)
{
startIndex += 1;
}
else
{
isFinish = true;
}
if (startIndex == inputValue.Count - 1)
{
index = startIndex;
isFinish = true;
}
break;
}
else
{
index = i - 1;
break;
}
}
}
}
else if (startIndex == inputValue.Count - 1)
{
index = startIndex;
isFinish = true;
}
else
{
isFinish = true;
}
return index;
}
}
}
