0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.