CODEWITHSUNDEEP
algorithmlanguage-agnostic
Marius
Marius

Reputation: 58949

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

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

Upvotes: 1

Views: 175

Answers (5)

Charles Ma
Charles Ma

Reputation: 49191

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)])

Upvotes: 1

dmckee --- ex-moderator kitten
dmckee --- ex-moderator kitten

Reputation: 101251

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.

Upvotes: 1

cletus
cletus

Reputation: 625237

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".

Upvotes: 3

Argalatyr
Argalatyr

Reputation: 4659

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.

Upvotes: 3

Sampson
Sampson

Reputation: 268414

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

Upvotes: 1

Related Questions