创建长度为 n 的布尔向量，其中 k 个真值分布良好

Question

问题是创建长度为 n 的布尔向量，其中 k true 个条目（和 n-k false 个条目）很好地分散在向量中.

如果k = 5和n = 8手动创建的解决方案是[1 0 1 1 0 1 0 1]或[1 0 1 0 1 0 1 1]等

条目分布不均的矢量示例为 [1 1 1 1 1 0 0 0 0]。

"well-dispersedness" 的一个可能标准是具有交替的零块和长度大致相同的块 - 特别是大小为 floor(n/k) 或 floor(n/k) + 1 的块和零块尺寸 floor(n/(n-k)) 或 floor(n/(n-k)) + 1.

如何创建这样的向量？

Answer 1

获取Bresenham algorithm的最简单实现，模拟绘制终点坐标(0,0)-(ones,zeros)的线段。这只是错误传播方法。

当算法产生X坐标变化（X-step）时，对应1-entry，Y-step对应0位。

def Distribute(ones, zeros):
    leng = ones + zeros
    err = leng // 2
    res = []
    for i in range(0, leng):
        err = err - ones
        if err < 0 :
            res.append(1)
            err = err + leng
        else:
            res.append(0)
    print(res)

Distribute(5,3)
[1, 0, 1, 0, 1, 1, 0, 1]

创建长度为 n 的布尔向量，其中 k 个真值分布良好

Create boolean vector of length n with k true values well dispersed

math

sequence