# Efficient bucketing of numbers

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.

• 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". – gnasher729 Jan 27 '18 at 21:13
• 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. – Alph0r Jan 27 '18 at 21:23
• Do you require the numbers in each bucket to be consecutive or not? If yes, please edit the question to specify that. – D.W. Jan 29 '18 at 1:40
• They don't need to be consecutive, they also don't have to be integers. – Alph0r Jan 30 '18 at 15:50

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).

• The question doesn't state a requirement that the numbers in a cluster need to be consecutive. – D.W. Jan 29 '18 at 1:41
• Non-consecutive numbers would increase the difference to the average in each cluster. – gnasher729 May 28 '18 at 8:21
• 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.... – D.W. May 28 '18 at 16:45