CODEWITHSUNDEEP
algorithm
Jean Paul Galea
Jean Paul Galea

Reputation: 1341

Evenly select N elems from array

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.

Upvotes: 12

Views: 4662

Answers (5)

Ajo
Ajo

Reputation: 396

Based on Rex's answer!

// Handles all the edge cases.
function select(array, selectionCount) {
    let iterationCount = array.length - 1;         // Number of iterations
    let expectedToBeSelected = selectionCount - 1; // Number of elements to be selected
    let resultsArray = [];                         // Result Array
    
    if (selectionCount < 1 || selectionCount > array.length) {
        console.log("Invalid selection count!");
        return resultsArray;
    }

    for (let i in array) {
        if (selectionCount == 1) {
            resultsArray.push(array[i]);
            break;
        }
        let selectedSoFar = Math.round(iterationCount * i / expectedToBeSelected);
        if (selectedSoFar < array.length) {
            resultsArray.push(array[selectedSoFar]);
        } else {
            break; // If selectedSoFar is greater than the length then do not proceed further.
        }
    }

    return resultsArray;
}

Upvotes: 1

Cam
Cam

Reputation: 15234

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(A[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)

Upvotes: 20

Rex Kerr
Rex Kerr

Reputation: 167901

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

Upvotes: 3

John
John

Reputation: 16007

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.

Upvotes: 1

AShelly
AShelly

Reputation: 35580

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.

Upvotes: 1

Related Questions