（几乎）均匀地从列表中选择项目

我有一个N元素的列表，我想要示例M (<= N)值尽可能均匀分布。更具体地说，假设选择应该最小化采样点之间的间距的差异。例如，让我们说我构造布尔索引阵列（即在python）选择的元素，（几乎）均匀地从列表中选择项目

我试图算法（来自此相似，但不同的问题：How do you split a list into evenly sized chunks?）：

q, r = divmod(N, M) 
indices = [q*jj + min(jj, r) for jj in range(M)]

有时候效果很好：

N=11 M=6 
good_index = [0 1 0 1 0 1 0 1 0 1 0] 

N=14 M=6 
good_index = [0 1 1 0 1 1 0 1 0 1 0 1 0 1]

在这里，第一个例子是微不足道的，因为数组可以平分。第二个例子不能平分，但点之间的间距尽可能相似（2,2,1,1,1,1）。

但往往效果很差：

N=16 M=10 
bad_index = [0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0] 

N=14 M=10 
bad_index = [0 1 0 1 0 1 0 1 0 0 0 0 0 0]

因为你必须在最后堆放值。

编辑1：woops，只是意识到每个列表上方技术上倒（0的应该是1的，反之亦然）......但还是应该传达正确的想法。

编辑2：上述算法往往工作从不是一些概念比较简单就像选择随机数更好的（即目视检查，

step = int(floor(N/M)) 
last = M * step # this prevents us from getting M+1 elements 
indices = [ii for ii in range(0, last, step)]

来源

2017-09-29 DilithiumMatrix

对于一个快速的方法，但看似随机看一看[Halton序列。]（https://en.wikipedia.org/wiki/Halton_sequence） –

@PrestonHager这是有趣的，但你怎么看它是有用吗？ – DilithiumMatrix

综观几次测试的结果（甚至是那些包括上面），问题是当M > N/2。也就是说，当超过一半的数值被采样时，但它对M < N/2很好，所以我现在使用的解决方案只是在M > N/2：

注意：这实际上是创建一个大小为N的屏蔽列表，它是虚假对于M元素尽可能均匀间隔。

import numpy as np 

def even_select(N, M): 
    if M > N/2: 
     cut = np.zeros(N, dtype=int) 
     q, r = divmod(N, N-M) 
     indices = [q*i + min(i, r) for i in range(N-M)] 
     cut[indices] = True 
    else: 
     cut = np.ones(N, dtype=int) 
     q, r = divmod(N, M) 
     indices = [q*i + min(i, r) for i in range(M)] 
     cut[indices] = False 

    return cut

如果它们存在，我仍然对更优雅的解决方案感兴趣。

来源

2017-09-29 17:58:05 DilithiumMatrix

我正在建议同样的事情。 –

（几乎）均匀地从列表中选择项目

回答

相关问题