Grouping data values so each group has the minimum range

Question

Apologies in advance if this is very obvious or has been asked elsewhere already - I'm not very 'maths-y' so not sure how to ask this intelligently.

What is the best way to group a set of data values into n groups, such that each groups has the smallest possible range?

Lets say my sample values are as follows:

{1, 2, 7, 8, 9, 15, 16, 16, 17, 18, 18, 20}

and I am wanting to create 3 groups with the least amount of spread in each group. We could do three groups like so:

{1, 2, 7}                         spread = 6
{8, 9}                            spread = 1
{15, 16, 16, 17, 18, 18, 20}      spread = 5
---------------------------------------------
                                   total = 12

Or, if we rework the first two groups we can reduce it:

{1, 2}                            spread = 1
{7, 8, 9}                         spread = 2
{15, 16, 16, 17, 18, 18, 20}      spread = 5
---------------------------------------------
                                   total = 8

So my question is: is there a mathematical way of determining how the groups should be formed?

As a reverse version of the question, is there a way to specify not the number of groups, but the maximum spread a group can have, and figure out the groups such that they don't exceed the spread?

This may have some crossover to programming algorithms so I will post it on Stack Overflow as well.

Answer 1

I think the second way you did it is fine.

Let us sort the values in ascending order so that $x_1\leq x_2 \leq \cdots \leq x_n$. The range of the whole data is then $$R=x_n-x_1\,.$$ Now we introduce a separator $s\in\{1,\ldots,n\}$ which defines the two groups $\{x_1,\ldots x_{s}\}$ and $\{x_{s+1},\ldots x_{n}\}$. Then the new range is $$R(s)=(x_s-x_1) + (x_n-x_{s+1})=R-(x_{s+1}-x_s)\,.$$ We want to make $R(s)=R-(x_{s+1}-x_s)$ as small as possible. To do it, we need to make $x_{s+1}-x_s$ as big as possible. So we have to take the value of $s$ which is associated with the biggest value of $x_{s+1}-x_s$, which is just the biggest gap between two consecutive values in the sorted data set.

For the case of more than two groups, I think you can argue similarly by introducing $s_1\leq s_2$ and computing $R(s_1,s_2)$, or you could argue recursively (first take the biggest gap and then the biggest remaining gap and so on).