Sample Elements with Evenly Distributed Value

Question

I have a programming problem, which can be described as follows:

given a sorted array x and a number k, I am asked to return another sorted array y, such that the elements in array y is evenly distributed by its VALUE (not index).

I am required to write an algorithm to solve this problem.

This problem should be formulated as following:

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

For example,

• x=[1,2,4,8,16,32,64,128] and k=3, I should have y=[1,64,128]
• x=[1,2,4,8,16,32,64,128] and k=5, I should have y=[1,16,32,64,128]
• x=[1,2,3,4,5,6,7] and k=4, I should have y=[1,3,5,7]

Thanks.

OK, I think I have found the solutions. The idea is

1. we pick two end elements from x and add to y;
2. we compute the step of those two end points as (x[-1]-x[0])/k-1;
3. we remove any elements which are smaller than x[0]+step from x, and elements which are larger than x[-1]-step from x;
4. k=k-2;
5. if k==0, terminate the algorithm; if k==1, find the middle elements;

The code is

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