创建长度为n的布尔向量，其中k个真值分布良好 [英] Create boolean vector of length n with k true values well dispersed

问题描述

问题是要创建长度为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个真值分布良好的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！