calculate minimum of max value of set of numbers

Question

Suppose to have a set of numbers:

$$S:=\{ 1,2,3,9,10,56,58,60\}$$

How can i group this number like this:

group 1:$\{1,2,3,9,10\}$

group 2:$\{56,58,60\}$

and then take "56" as minimum value of group with highest value?

thanks ;-)

Answer 1

There isn't, to my knowledge, a simple "do this thing and get the answer" kind of algorithm for this problem, but there are some algorithms capable of splitting up the set to be mostly "well-divided" into sort of sensible groups.

---

If the set has not repeats, there is a good method for sorting based on linear differences, but it relies heavily on the data already being sort of bunched together. It works kind of like this:

1. Sort your list from least to greatest
2. Take the first differences $x_{i+1}-x_i=\delta_i$
3. Take the second differences $\delta_{i+1}-\delta_i=\delta^*_i$
4. Find $i$ such that $|\delta^*_i|>|\delta^*_j|$ for $j\neq i$.
5. If $|\delta_i|\geq|\delta_{i+1}|$, split the set into $S_1$ and $S_2$ such that $x_j\in S_1$ for $j\leq i+1$. Otherwise, split it so that $x_j\in S_1$ for $j\leq i$.
6. Repeat until the desired "clustering" is achieved.

---

Another algorithm exists that relies heavily on order of magnitude. For strictly positive data, the algorithm works kind of like this:

1. Take the natural logarithm of each $x_i$ to get $m_i=\ln(x_i)$
2. If $\lfloor y_i\rfloor=\lfloor y_j\rfloor$, then $y_i$ and $y_j$ go in the same subset.
3. If higher similarity is desired, split each subset using $ky_i$ for some constant $k>1$
4. If lower similarity is allowed, split on $ky_i$ for $0<k<1$
5. Run steps 1 and 2 with several values of $k$ to find "optimal" arrangement

---

Finally, you could extend the second method by taking $z_i=\ln|x_i|$ and clustering these, which would allow negative values. This also requires an added rule: if $x_i$ and $x_j$ have different signs, they go in different sets.

---

Once you have the subsets divided up, the process for finding the desired value is REALLY simple:

1. Find the minimum value in each set.
2. Find the maximum among these values.