0
$\begingroup$

Assume we have a sorted list of n numbers, I want to map those numbers to m buckets or clusters. For each bucket the average of all numbers in that bucket will be computed. The task is to find a mapping, so that the difference between those cluster averages and the original numbers is minimal.

Example:
List: [1, 2, 3, 4], desired number of buckets: 2
Optimal Solution:
Bucket 0: [1, 2], Average: 1.5, Difference: abs(2 - 1.5) + abs(1 - 1.5) = 1
Bucket 1: [3, 4], Average: 3.5, Difference: abs(4 - 3.5) + abs(3 - 3.5) = 1
Overall Difference: 2

I know how to create a mapping by brute force, but I would need a more efficient algorithm.

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ What exactly do you mean by "brute force"? Exponential time, polynomial time? I can think of a nice polynomial time algorithm that I would call "brute force". $\endgroup$ – gnasher729 Jan 27 '18 at 21:13
  • $\begingroup$ My solution would be exponential in the number of clusters. Basicaly I would define indexes at which the list gets split, in the example the index would be 2. I would then try every combination of border indexes, I think the complexity of that is n^m. $\endgroup$ – Alph0r Jan 27 '18 at 21:23
  • $\begingroup$ Do you require the numbers in each bucket to be consecutive or not? If yes, please edit the question to specify that. $\endgroup$ – D.W.♦ Jan 29 '18 at 1:40
  • $\begingroup$ They don't need to be consecutive, they also don't have to be integers. $\endgroup$ – Alph0r Jan 30 '18 at 15:50
1
$\begingroup$

Polynomial time is not too difficult.

A "cluster" contains a sequence of 1 or more consecutive numbers from your list. The "badness" of a cluster is defined as the sum of absolute differences between the numbers, and the average of the numbers in the cluster. A sequence of clusters is a list of clusters, containing consecutive numbers from the list starting with the first one. And the "badness" of a sequence of clusters is the sum of badnesses of the individual clusters.

First get a reasonable upper bound for the best clustering to avoid unnecessary work: Just cluster the n numbers into m buckets of equal or almost equal size, then calculate the badness of this sequence of clusters. Call the result B. You might also calculate the badness of a sequence of clusters created by splitting where the largest gaps between consecutive numbers are.

Now for 1 ≤ m' ≤ m, and for 1 ≤ n' ≤ n - (m - m'), calculate the best sequence of m' clusters covering exactly the first n' numbers, and its badness. For m' = 1 that's trivial, because the cluster consists of the numbers 1 to n'. For m' > 1 it is more difficult: The best clustering using m' clusters to cover 1 to n' consists of the best clustering using m'-1 clusters covering 1 to n'' for some n'' < n', plus the cluster n''+1 .. n'. You calculate the badness of this for n'' = n'-1 down to m'-1. All these badnesses can be calculated in O (n), so the best badness for m' and n' can be found in O (n).

In total, you find the optimal badness for m clusters covering 1 to n in $O (n^3)$. If you take advantage of the upper bound B found earlier, and consider that any result that leads to a badness > B can be ignored, you can probably save significant amount of time.

PS. How to find the badness for different clusters each in constant time: Let's say you want to find the badness of a cluster covering the numbers from l to r, for l = r, r-1, r-2, ..., 1. Start with l = r. The sum of items in the cluster is $C = a_l$. The badness is 0. Let s = l. Then the sum of items at indices < s is $S = 0$.

Now replace l with l-1. Increase C and S by $a_l$. The average A of items in the cluster is C / (r - l + 1). As long as $a_{s-1} ≥ A$ replace s with s-1, and subtract $a_s$ from S. The badness in the cluster is C - 2S + ((2s - l - n - 1)A (unless I made some mistake).

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ The question doesn't state a requirement that the numbers in a cluster need to be consecutive. $\endgroup$ – D.W.♦ Jan 29 '18 at 1:41
  • $\begingroup$ Non-consecutive numbers would increase the difference to the average in each cluster. $\endgroup$ – gnasher729 May 28 '18 at 8:21
  • $\begingroup$ Ahh. That makes intuitive sense. Do you have a proof for it? i.e., a proof that in the optimal solution the numbers in the cluster will always be consecutive? Or, equivalently, that a cluster of non-consecutive numbers will always have a larger absolute difference than a cluster of consecutive numbers of the same size? Just wondering if there could be some tricky case where this isn't optimal.... $\endgroup$ – D.W.♦ May 28 '18 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.