# Algorithm for selecting a sample that's as spread out as possible?

I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as close to evenly distributed as possible).

E.g. if the dates are [1, 2, 3, 4, 100] and I want to sample 3 elements, the ideal sample would be [1, 50.5, 100] and the closest available dates are [1, 4, 100].

Is this a known problem with an existing algorithm?

## bumped to the homepage by Community♦yesterday

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

• Could you define your goal more clearly? Could you give more examples? For example, if the date are [1,2,3,4,5,6,7,8,9,10, 20,95,99,100] and you want to sample 5 elements, what should happen? What will be done to the chosen samples? – Apass.Jack Jun 16 at 21:16

I assume that for dates $$d_1\leq d_2\leq\cdots\leq d_n$$ you want $$k>1$$ samples of minimal total absolute distance from the ideal sample points $$s_i=d_1+(i-1)(d_n-d_1)/(k-1)$$, $$i\in[k]$$.
If you can repeat elements, just sample at $$\operatorname{argmin}_{j\in[n]}|d_j-s_i|$$ for each $$i\in[n]$$.
Without repeating elements the following dynamic program solves your problem in time $$O(n^3)$$ and space $$O(n^2)$$: let $$M(i,j)$$ be the minimal total absolute distance for $$k-i+1$$ samples chosen from $$a_j,\ldots,a_n$$ from the ideal samples $$s_i,\ldots,s_k$$. Distance $$M$$ satisfies \begin{align*} M(i,j) = \begin{cases} \min_{j\leq j'\leq n} |d_{j'}-s_i|+M(i+1,j'+1), & \text{i\leq k, j\leq n, }\\ 0, & \text{i>k},\\ \infty, & \text{otherwise}, \end{cases} \end{align*} and $$M(1,1)$$ is the minimum solution value.