问题描述
问题是要创建长度为n的布尔向量，并在其中分散k true个条目(和n-k false个条目).
The problem is to create boolean vector of length n with k true entries (and n-k false entries) well dispersed in the vector.
如果k = 5和n = 8手动创建的解决方案是[1 0 1 1 0 1 0 1]或[1 0 1 0 1 0 1 1]等.
If k = 5 and n = 8 manually created solutions are [1 0 1 1 0 1 0 1] or [1 0 1 0 1 0 1 1] etc.
[1 1 1 1 1 0 0 0 0]是具有不充分分散的条目的向量的示例.
An example for a vector with entries that are not well dispersed would be [1 1 1 1 1 0 0 0 0].
可能存在的良好分散性"标准是交替的零块和大致相同长度的块-特别是大小为floor(n/k)或floor(n/k) + 1的一个块和大小为floor(n/(n-k))的零块或floor(n/(n-k)) + 1.
A possible criterium for "well-dispersedness" is having alternating blocks of zeros and ones of roughly the same length - specifically with one-blocks of size floor(n/k) or floor(n/k) + 1 and zero-blocks of size floor(n/(n-k)) or floor(n/(n-k)) + 1.
如何创建这样的向量?
推荐答案
获取的最简单实现Bresenham算法，并模拟端坐标为(0,0)-(ones,zeros)的线段的绘制.这只是错误传播方法.
Get the simplest implementation of Bresenham algorithm, and simulate drawing of line segment with end coordinates (0,0)-(ones,zeros). This is just error-propagation approach.
算法生成X坐标(X步)的变化时，它对应于1项，Y步对应于零位.
When algorithm generates change of X-coordinate (X-step), it corresponds to 1-entry, Y-step corresponds to zero bit.
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个真值分布良好的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！