6

I really need an master of algorithm here! So the thing is I got for example an array like this:

[
    [870, 23]
    [970, 78]
    [110, 50]
]

and I want to split it up, so that it looks like this:

// first array
[
    [970, 78]
]
// second array
[
    [870, 23]
    [110, 50]
]

so now, why do I want it too look like this?

Because I want to keep the sum of sub values as equal as possible. So 970 is about 870 + 110 and 78 is about 23 + 50. So in this case it's very easy because if you would just split them and only look at the first sub-value it will already be correct but I want to check both and keep them as equal as possible, so that it'll also work with an array which got 100 sub-arrays! So if anyone can tell me the algorithm with which I can program this it would be really great!

Scales:

  • ~1000 elements (sublists) in the array
  • Elements are integers up to 10^9

I am looking for a "close enough solution" - it does not have to be the exact optimal solution.

amit
  • 175,853
  • 27
  • 231
  • 333
noob
  • 8,982
  • 4
  • 37
  • 65
  • 2
    possible duplicate of [How to optimally divide an array into two subarrays so that sum of elements in both are same . otherwise give an error](http://stackoverflow.com/questions/5898104/how-to-optimally-divide-an-array-into-two-subarrays-so-that-sum-of-elements-in-b) – Felix Kling Oct 28 '12 at 18:59
  • 1
    @FelixKling no that's not a dublicate, he would like to divide one array in two sub arrays based on one sum and not on two sums, there're actually a lot more questions out there which which are asking this. – noob Oct 28 '12 at 19:01
  • Mmmh, I'd still say it's basically the same problem, just harder ;) The answer links to http://en.wikipedia.org/wiki/Partition_problem which should give you a good start for that problem. – Felix Kling Oct 28 '12 at 19:03
  • @FelixKling yeah that's right but not just a little harder, it's very much harder to solve. – noob Oct 28 '12 at 19:04
  • 1
    @FelixKling This is not partition problem, the other answers are wrong as well. Partition problem is when you need to take a subset from the array, in here you only need to chose the "partition point" - you take a subarray, and not a subset. The brute force solution is `O(n^2)` by checking each possible "partition" point, and checking the sums. (Unless of course, it can be any subset, and not a subarray - and then it is the partition problem, but then the question is just confusing) – amit Oct 28 '12 at 19:06
  • For example, why don't sum each subarray and then optimise for that sum, i.e. for `[1048, 893, 160]`. I have no mathematical proof but my intuition is that this would achieve a similar result. – Felix Kling Oct 28 '12 at 19:07
  • @amit: So you mean you pick an index and compare the sum of the numbers before and after that index? That's not evident from the question IMO, but that might be because of my or the OP's interpretation/usage of terminology. – Felix Kling Oct 28 '12 at 19:11
  • @FelixKling the problem here is that if for example the first value is very huge and the second value is very small the second value would not have any effect on how the aray get split up, so it would be more or less ignored. – noob Oct 28 '12 at 19:13
  • http://chat.stackoverflow.com/rooms/18683/question-13111970 – noob Oct 28 '12 at 19:15
  • @FelixKling: The suggested approach for brute force is not answering this question, but the "partition problem" (not really partition problem) where you actually need subarrays and not subsets. I think there is also `O(nlogn)` solution for this problem. but I understand from the question that he is looking for a *sub-array* - specifically, "split an array" indicate a single splitting point and not finding a subset, IMO. – amit Oct 28 '12 at 19:15

4 Answers4

2

First, as already established - the problem is NP-Hard, with a reduction form Partition Problem.

Reduction:
Given an instance of partition problem, create lists of size 1 each. The result will be this problem exactly.

Conclusion from the above:
This problem is NP-Hard, and there is no known polynomial solution.

Second, Any exponential and pseudo polynomial solutions will take just too long to work, due to the scale of the problem.

Third, It leaves us with heuristics and approximation algorithms.

I suggest the following approach:

  1. Normalize the scales of the sublists, so all the elements will be in the same scale (say, all will be normalzied to range [-1,1] or all will be normalized to standard normal distribution).
  2. Create a new list, in which, each element will be the sum of the matching sublist in the normalized list.
  3. Use some approximation or heuristical solution that was developed for the subset-sum / partition problem.

The result will not be optimal, but optimal is really unattanable here.

amit
  • 175,853
  • 27
  • 231
  • 333
2

From what I gather from the discussion under the original post, you're not searching for a single splitting point, but rather you want to distribute all pairs among two sets, such that the sums in each of the two sets are approximately equal.

Since a close enough solution is acceptable, maybe you could try an approach based on simulated annealing? (see http://en.wikipedia.org/wiki/Simulated_annealing)

In short, the idea is that you start out by randomly assigning each pair to either the Left or the Right set. Next, you generate a new state by either

  • a) moving a randomly selected pair from the Left to the Right set,
  • b) moving a randomly selected pair from the Right to the Left set, or
  • c) doing both.

Next, determine if this new state is better or worse than the current state. If it is better, use it. If it is worse, take it only if it is accepted by the acceptance probability function, which is a function that initially allows worse states to be used, but favours them less and less as time moves on (or the "temperature decreases", in SA terms). After a large number of iterations (say 100.000), you should have a pretty good result.

Optionally, rerun this algorithm multiple times because it may get stuck in local optima (although the acceptance probability function attempts to counter this).

Advantages of this approach are that it's simple to implement, and you can decide for yourself how long you want it to continue searching for a better solution.

Leon Bouquiet
  • 4,159
  • 3
  • 25
  • 36
1

I'm assuming that we're just looking for a place in the middle of the array to split it into its first and second part.

It seems like a linear algorithm could do this. Something like this in JavaScript.

arrayLength = 2;
tolerance = 10;

// Initialize the two sums.
firstSum = [];
secondSum = [];
for (j = 0; j < arrayLength; j++)
{
   firstSum[j] = 0;
   secondSum[j] = 0;
   for (i = 0; i < arrays.length; i++)
   {
      secondSum += arrays[i][j];
   }
}

// Try splitting at every place in "arrays".
// Try to get the sums as close as possible.
for (i = 0; i < arrays.length; i++)
{
   goodEnough = true;
   for (j = 0; j < arrayLength; j++)
   {
      if (Math.abs(firstSum[j] - secondSum[j]) > tolerance)
         goodEnough = false;
   }

   if (goodEnough)
   {
      alert("split before index " + i);
      break;
   }

   // Update the sums for the new position.
   for (j = 0; j < arrayLength; j++)
   {
      firstSum[j] += arrays[i][j];
      secondSum[j] -= arrays[i][j];
   }
}
noob
  • 8,982
  • 4
  • 37
  • 65
Hew Wolff
  • 1,489
  • 8
  • 17
  • The example shows an element from the middle of the array forming array1, and the rest of the array forming array 2. So not looking to split in one place. – James Oct 28 '12 at 19:55
0

Thanks for all the answers, the bruteforce attack was a good idea and NP-Hard is related to this too, but it turns out that this is a multiple knapsack problem and can be solved using this pdf document.

noob
  • 8,982
  • 4
  • 37
  • 65