Примеры элементов с равномерно распределенным значением

Question

У меня есть проблема программирования, которая может быть описана следующим образом:

учитывая отсортированный массив x и число k, меня просят возвратить другой отсортированный массив y, чтобы элементы в массиве y равномерно распределялись по его VALUE (не индексу).

Мне необходимо написать алгоритм для решения этой проблемы.

Эта проблема должна быть сформулирована следующим образом:

\max_{x\in y}{\min_{a,b\in x}{|a-b|}}

Например,

• x = [1,2,4,8,16,32,64,128] и k=3, у меня должно быть y = [1,64,128]
• x = [1,2,4,8,16,32,64,128] и k=5, у меня должно быть y = [1,16,32,64,128]
• x = [1,2,3,4,5,6,7] и k=4, у меня должно быть y=[1,3,5,7]

Благодарю.

ОК, я думаю, что нашел решения. Идея

1. мы выбираем два конечных элемента из x и добавляем к y;
2. мы вычисляем шаг этих двух конечных точек как (x[-1]-x[0])/k-1;
3. мы удаляем все элементы, которые меньше x[0]+step из x, и элементы, которые больше x[-1]-step из x;
4. K = K-2;
5. если k==0, завершить алгоритм; если k == 1, найдите средние элементы;

Код

def sample_element_even(idx, k, val=None):
"""
this function returns k elements from idx (which is a list), such that the samples's value (val) are evenly
distributed
note idx should be sorted. If idx is comparable, val will be used instead
"""
if val is None:
    val=idx
# number of element remains
m=k
n=len(idx)
left=0
right=n-1
# all elements found
if m==0:
    return []
# special case
if m==1:
    middle=bisect.bisect(val, (val[left]+val[right])/2.0)
    if val[middle]+val[middle-1]>val[left]+val[right]:
        result=[idx[middle-1]]
    else:
        result=[idx[middle]]
    return result
# normal case
result=[None]*k
while m>0:
    # normal case
    # pick the two ends first
    result[(k-m)/2]=idx[left]
    result[k-1-(k-m)/2]=idx[right]
    # compute the step
    step=(val[right]-val[left])/(m-1.0)
    m=m-2
    # all elements found
    if m==0:
        break
    # only one elements left, choose its middle
    if m==1:
        middle=bisect.bisect(val, (val[left]+val[right])/2.0)
        if val[middle]+val[middle-1]>val[left]+val[right]:
            result[(k-m)/2]=idx[middle-1]
        else:
            result[(k-m)/2]=idx[middle]
        break
    left=bisect.bisect(val, val[left]+step)
    right=bisect.bisect(val, val[right]-step)
return result