How do I evenly pick every m value from an array, when m is a decimal?

Question

Lets say I have an array of length n and I want to pick k values from it, evenly, starting from 0. If k divides n, then this would be easy, but if k does not divide n, then I need to vary the value m I increment the array pointer with. How would you do this?

For example, if m=1.5 then I want to pick the following numbers: var arr = array(0,1,2,3,4,5,6,7,8); arr.every(1.5); //returns 0,1,3,4,6,7

I don't need to know what happens if k is larger than n

Answer 1

You'd have to round up or down to the nearest whole number.

Answer 2

you'll need to decide whether the specification "k", or "evenly", is more important, because when k does not divide n, one will have to be sacrificed.

Answer 3

You might look at the Bresenham's line algorithm, which actually does something akin to that.

The line algorithm, chooses an appropriate number of steps at roughly even spacing that looks very smooth and natural, you just need to adapt it to sample values from the array where it would have stepped the line.

Answer 4

Firstly you have to define what "evenly" means. If n = 12 and k = 3 then are the correct values (1, 5, 9) (starting from 1) or, say, (1, 7, 12). Obviously they're going to have different results.

In some ways this is similar to the problem of scaling/stretching images and rasterizing lines (Wu's algorithm is typically used for anti-aliasing in modern graphics but Bresenham's is still important and more relevant for this) and is solvable with Bresenham's line algorithm.

1         *
2       **
3     **
4   **
5 **
6*
 1234567890

Note: I didn't actually work out if these were the correct values. This is merely illustrative.

In this example, you're creating a diagonal line across a 6x10 box. Another way to look at this algorithm is to say n = 10, k = 6 and every time the line increments you have one of your values so (1,2,4,6,8,10).

but it all depends on how you define "evenly".

Answer 5

Keep a floating point index that increments by m. when you need to get an item from the array, floor the index into an integer.

i = 0.0
inc = n/(float)k

while(i < n)
   i += inc
   solutionSet.add(array[floor(i)])