sample - 値が均等に分散されたサンプル要素

Question

次のように説明できるプログラミングの問題があります。

ソートされた配列 x と数値 k が与えられた場合、別のソートされた配列 y を返すように求められます。これにより、配列 y の要素がその値 (インデックスではなく) によって均等に分散されます。

この問題を解決するアルゴリズムを書く必要があります。

この問題は次のように定式化する必要があります。

\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] にする必要があります

ありがとう。

OK、解決策を見つけたと思います。アイデアは

1. x から 2 つの end 要素を選択し、y に追加します。
2. これらの 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