从阵列中均匀选择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
数组[0,1,2,3,4,5,6,7],5元:0,2,3或4,5 ,7

是的,我想总是包括第一个和最后一个元素.

编辑2:

我所想的是......第一个+最后一个元素,然后使用中值继续工作.虽然我在试图这样做时遇到困难/困惑.

我会看看你发布的算法.谢谢!

编辑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为浮点数,并在迭代数组时将其舍入为多次step.

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