Choose m uniformly spaced elements from a sequence of length n

Question

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

The choice should be fair / determinate - equally many from each subsection.

With m = 10, n = 20 it's easy: just grab every second item. But how to do this in the general case? Do I need to calculate the LCD?

Answer 1

Here is a quick example:

from math import ceil def takespread(sequence, num): length = float(len(sequence)) for i in range(num): yield sequence[int(ceil(i * length / num))] 

math.ceil used because without it, the selected indexes will be too weighted relative to the beginning of each implicit subsection and, as a result, the list as a whole.

Answer 2

You probably need a Bresenham line algorithm . Selecting elements m uniformly from n equivalent to drawing a row in the m x n grid of discrete pixels. Assume x coordinate at 0 .. n-1 and y coordinate 0 .. m-1 and continue as if you were drawing a line between (0,0) and (n-1, m -1). When y coordinates change, select an element from the x index.

UPD: But it seems that this simple function is enough for 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] 

Answer 3

Use a loop (int i = 0; i <m; i ++)

Then, to get the indices you need, Ceil (i * m / n).

Answer 4

I am working on clinical use and have found all the answers above to have varying degrees of bias. Here's another solution that works well even in a circle. That is, even if the last number wraps around when you work with degrees 0 ° = 360 °.

 import numpy as np m = 51 # Generate intervals epts = np.linspace(0,360,m+1,endpoint=True) # Create the halfsteps between intervals (One would have sufficed) halfsteps = (epts[1:] - epts[:-1]) / 2 # Find the midpoints midpoints = epts[:-1] + halfsteps # Make an unbiased rounding results = np.around(midpoints, decimals=0) 

Answer 5

This will always select the first and last items:

 which_idxs = lambda m, n: np.rint( np.linspace( 1, n, min(m,n) ) - 1 ).astype(int) evenly_spaced = np.array( your_list )[which_idxs(m,n)] 

This will select only a maximum of n elements if m is greater than n. If you really want it to be evenly distributed throughout the array, even at the ends, then this would be the following:

 which_idxs = lambda m, n: [idx for idx in np.rint( np.linspace( 1-n/(2*min(m,n)), n+n/(2*min(m,n)), min(m,n)+2 ) - 1 ).astype(int) if idx in range(n)] evenly_spaced = np.array( your_list )[which_idxs(m,n)] 

Which gives you something like this:

 >>> np.array( [1, 2, 3, 'a', 'b', 'c'] )[which_idxs(m,n)] Out: array(['2', 'b'])