algorithm - 从数组中平均选择 N 个元素

Question

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

说我有:

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

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

我很确定有一个为此定义的算法，一直在尝试搜索，我看了一下算法简介但找不到任何满足我需求的东西(可能被忽略了) )

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

注意:我不能只从上面的例子中选择偶数元素..

另外几个例子；

数组[0,1,2,3,4,5,6], 3个元素；我需要得到 0,3,6
数组[0,1,2,3,4,5], 3 个元素；我需要得到 0、2 或 3，以及 5

编辑:

更多例子:
数组 [0,1,2]，2 个元素:0,2
array [0,1,2,3,4,5,6,7], 5 elems : 0,2, 3 or 4, 5,7

是的，我想始终包含第一个和最后一个元素。

编辑 2:

我当时的想法是 .. first + last element，然后使用中间值逐步增加。虽然我在尝试这样做时遇到了困难/困惑。

我会看看您发布的算法。谢谢!

编辑 3:

这是使用 PHP 的 incrediman 解决方案的增强版本。也适用于关联数组，同时保留键。

<?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;
}

?>

你或许可以实现一个 Iterator但我不需要走那么远。

Answer 1

伪代码:

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 转换为整数或在开头对其进行舍入。但是，为了确保提取正确的元素，您必须将 step 声明为 float ，并且 round step 的倍数/em> 当您遍历数组时。

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