Evenly select N elems from array

Question

Hi,

I need to evenly select n elements from an array. I guess the best way to explain is by example.

say I have:

array [0,1,2,3,4] and I need to select 3 numbers.. 0,2,4.

of course, if the array length <= n, I just need to return the whole array.

I'm pretty sure there's a defined algorithm for this, been trying to search, and I took a look at Introduction to algorithms but couldn't find anything that met my needs (probably overlooked it)

The problem I'm having is that I can't figure out a way to scale this up to any array [ p..q ], selecting N evenly elements.

note: I can't just select the even elements from the example above..

A couple other examples;

array[0,1,2,3,4,5,6], 3 elements ; I need to get 0,3,6
array[0,1,2,3,4,5], 3 elements ; I need to get 0, either 2 or 3, and 5

EDIT:

more examples:
array [0,1,2], 2 elems : 0,2
array [0,1,2,3,4,5,6,7], 5 elems : 0,2, either 3 or 4, 5,7

and yes, I'd like to include first and last elements always.

EDIT 2:

what I was thinking was something like .. first + last element, then work my way up using the median value. Though I got stuck/confused when trying to do so.

I'll take a look at the algo you're posting. thanks!

EDIT 3:

Here's a souped up version of incrediman solution with PHP. Works with associative arrays as well, while retaining the keys.

<?php

/**
 * Selects $x elements (evenly distributed across $set) from $set
 *
 * @param $set array : array set to select from
 * @param $x int     : number of elements to select. positive integer
 *
 * @return array|bool : selected set, bool false on failure
 */
///FIXME when $x = 1 .. return median .. right now throws a warning, division by zero

function select ($set, $x) {
    //check params
    if (!is_array($set) || !is_int($x) || $x < 1)
        return false;

    $n = count($set);

    if ($n <= $x)
        return $set;

    $selected = array ();
    $step     = ($n - 1) / ($x - 1);
    $keys     = array_keys  ($set);
    $values   = array_values($set);

    for ($i=0; $i<$x; $i++) {
        $selected[$keys[round($step*$i)]] = $values[round($step*$i)];
    }

    return $selected;
}

?>

You can probably implement an Iterator but I don't need to take it that far.

Answer 1

Your step size is (ArraySize-1)/(N-1).
Just add the step size to a floating point accumulator, and round off the accumulator to get the array index. Repeat until accumulator > array size.

Answer 2

Let n+1 be the number of elements you want, already bounded to the length of the array.

Then you want elements at indices 0/n, 1/n, ..., n/n of the way to the end of the array.

Let m+1 be the length of the array. Then your indices are round(m*i/n) (with the division done with floating point).

Answer 3

It looks like you want to include both the first and last elements in your list.

If you want to pull X items from your list of N items, your step size will be (N-1)/(X-1). Just round however you want as you pull out each one.

Answer 4

Enjoy! (pseudo-code):

function Algorithm(int N,array A)
    float step=(A.size-1)/(N-1)       //set step size

    array R                           //declare return array

    for (int i=0, i<N, i++)
        R.push(array[round(step*i)])  //push each element of a position which is a
                                      //multiple of step to R

    return R

Probably the easiest mistake to make here would be to cast step as an integer or round it at the beginning. However, in order to make sure that the correct elements are pulled, you must declare step as a floating point number, and round multiples of step as you are iterating through the array.

Tested example here in php:

<?

    function Algorithm($N,$A){

        $step=(sizeof($A)-1)/($N-1);
        for ($i=0;$i<$N;$i++)
            echo $A[round($step*$i)]." ";
        echo "\n";
    }

    //some of your test cases:
    Algorithm(3,array(1,2,3));
    Algorithm(5,array(0,1,2,3,4,5,6,7));
    Algorithm(2,array(0,1,2));
    Algorithm(3,array(0,1,2,3,4,5,6));
?>

Outputs:
1 2 3 
0 2 4 5 7 
0 2 
0 3 6 

(you can see your test cases in action and try new ones here: http://codepad.org/2eZp98eD)