-1

The problem is to create boolean vector of length n with k true entries (and n-k false entries) well dispersed in the vector.

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.

An example for a vector with entries that are not well dispersed would be [1 1 1 1 1 0 0 0 0].

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.

How to create such a vector?

Moritz Schauer
  • 1,378
  • 9
  • 19

1 Answers1

1

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.

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]
MBo
  • 77,366
  • 5
  • 53
  • 86
  • That is nice! Is this version of Bresenham's algorithm guaranteed to create a vector with exact `k` number of ones or do I need to check the result? – Moritz Schauer Nov 08 '19 at 21:33
  • From this an answer for https://stackoverflow.com/a/58774185/2556061 can be derived – Moritz Schauer Nov 08 '19 at 22:05
  • 1
    @mschauer I hope - yes, [random tests passed](https://ideone.com/Ka5kb1). But it is possible to use another implementation with explicit loop by X – MBo Nov 09 '19 at 04:02