从数组中均匀选择N个元素 [英] Evenly select N elems from array

问题描述

我需要均匀从数组中选择 n 个元素。我想最好的解释方法是举例。

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

说我有：

数组[0,1 ，2,3,4]，我需要选择3个数字。.0,2,4。

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

当然，如果数组长度< = n ，我只需要返回整个数组。

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)

我遇到的问题是我无法找出一种将其扩展到任意数组[p..q]的方法，选择N个均匀的元素。

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.

注意：我不能只是

另外两个示例；

array [0,1 ，2,3,4,5,6]，3个元素;我需要得到0,3,6

array [0,1,2,3,4,5]，3个元素;我需要得到0，即2或3，以及5

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

编辑：

更多示例：

数组[0,1,2]，2个元素：0,2

数组[0,1,2,3,4,5,6,7]，5个元素：0 ，2，3或4，5,7

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.

编辑2：

我当时想的是.. first + last元素，然后使用中位数进行计算。尽管这样做会令我感到困惑/困惑。

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!

编辑3：

这是 incrediman 解决方案的增强版本使用PHP。

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.

推荐答案

享受！ （伪代码）：

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

在这里可能最容易犯的错误就是投下步骤作为整数或将其四舍五入。但是，为了确保提取正确的元素，必须声明 step 作为浮点数，并舍入 <$ c的整数倍$ c> step ，当您遍历数组时。

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.

在php中测试过的示例：

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 

（您可以查看正在使用的测试用例，并在此处尝试新的用例： http://codepad.org/2eZp98eD ）

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

这篇关于从数组中均匀选择N个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！