# Selecting k numbers out of N sorted numbers to a minimize a condition/Formula

A sorted list of $\mathbf N$ numbers is given.

$X_1$ $\le$ $X_2$ $\le$ $X_3$ $\le$ .... $\le$ $X_N$

Select $\mathbf K$ Numbers - $Y_1$ , $Y_2$ , $Y_3$ , ..... , $Y_K$ - Such that the following value is minimised.

$$\sum_{1 \le i \lt j \le k} |(Y_i-Y_j)|$$ Let's call it FORMULA.

• My Approach

I Select them such that $Y_1$ $\le$ $Y_2$ $\le$ $Y_3$ $\le$ ..... $\le$ $Y_K$ . Now we need to minimize

$$\sum_{1 \le i \lt j \le k} (Y_i-Y_j)$$

• REAL DOUBT

I m only considering $\mathbf K\,consecutive$ elements(could start from any position).

So, is it possible that the left out cases(i.e K non-consecutive elements ) give a lower value(for the formula above) than the cases i consider ?

• Bonus Question

To calculate the FORMULA for a particular case $\;Y_1$ $\le$ $Y_2$ $\le$ $Y_3$ $\le$ ..... $\le$ $Y_K$

I create another list with $Z_j$= $(Y_{j+1} - Y_j)$ ---> Equation1

FORMULA = $\sum_{i=1}^{(n-1)}i(k-i)Z_i$ ---> Equation2

Is this Correct?

• EDIT 1

In my opinion , If there are such instances, they would consist of equal elements in the original list with N numbers.

• possible duplicate of Minimisation of a distance sum covering the REAL DOUBT Oct 22, 2013 at 16:11
• The bonus question formula is not correct. If all the gaps are the same size, it would be correct without the $(k-i)$ term Oct 22, 2013 at 16:15
• @RossMillikan could u give an exmaple where it fails? For List Y -10,20,30,40 (K=4) formula gives 100 . which is correct i think. Oct 22, 2013 at 16:25
• Your edit to Equation 1 has not solved the problem. On the right side $j$ is a dummy variable, so the value does not depend on $j$. Oct 22, 2013 at 17:58
• Yes, that is fine Oct 23, 2013 at 7:57