python - Choose m evenly spaced elements from a sequence of length n

Question

I have a vector/array of n elements. I want to choose m elements.

The choices must be fair / deterministic -- equally many from each subsection.

With m=10, n=20 it is easy: just take every second element. But how to do it in the general case? Do I have to calculate the LCD?

Answer 1

You probably need Bresenham's line algorithm. Choosing m elements uniformly from n is equivalent to drawing a line in mxn discrete pixel grid. Assume x coordinate in 0..n-1 and y coordinate 0..m-1, and proceed like if you were drawing a line between (0,0) and (n-1,m-1). Whenever y coordinate changes, pick an element from index x.

UPD: But it seems that this simple function will suffice you:

>>> f = lambda m, n: [i*n//m + n//(2*m) for i in range(m)]
>>> f(1,20)
[10]
>>> f(2,20)
[5, 15]
>>> f(3,20)
[3, 9, 16]
>>> f(5,20)
[2, 6, 10, 14, 18]