均匀地从数组中选择N个元素

我需要均匀选择n数组中的元素。我想最好的解释方式是举例。均匀地从数组中选择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个elems的：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但我不需要那么远。

来源

2010-03-15 Jean Paul Galea

你需要什么号来选择？对你的模式更具体。 – 2010-03-16 00:01:30

我想你需要更多的例子，因为我仍然不明白你想要做什么。那么如何选择更长的阵列和不同数量的元素呢？ – 2010-03-16 00:01:54

如果我正确读取它，OP想要选择一些数组元素，其索引遵循一些规则模式。我认为雷克斯克尔的回答可能会更好地解释这里提出的问题。 – bta 2010-03-16 00:09:27

享受！（伪代码）：

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）

来源

2010-03-16 00:15:16 Cam

在哪里使用“step”？我只看到它的声明。 – 2010-03-16 00:26:37

@ nin， - 错字。现在应该更有意义。 – Cam 2010-03-16 00:29:35

该死的伙计，检查了键盘的链接，根据输入=>输出，正是我正在寻找。明天我会研究这个功能并调整一下，因为现在已经太晚了。队友的欢呼声！ – 2010-03-16 00:58:45

您的步长是（ArraySize-1）/（N-1）。
只需将步长添加到浮点累加器，然后四舍五入累加器即可获取数组索引。重复，直到累加器>数组大小。

来源

2010-03-16 00:04:23 AShelly

让n+1为您想要的元素的数量，已经绑定到数组的长度。

然后，您需要索引0/n,1/n，...，n/n中元素到数组末尾的方式。

令m+1为数组的长度。然后你的索引是round(m*i/n)（用浮点完成分割）。

来源

2010-03-16 00:04:41

这是不正确的。对于长度为m的'0'索引数组，最后一个索引应该是m-1而不是m，因此索引应该是round（（m-1）* i/n）如上所述）。 – Clueless 2010-03-16 00:10:05

在每次迭代中计算'round（m * i/n）'（或'round（（m-1）* i/n）'）效率不高吗？其实没关系 - 我误读了帖子。你们只是指出了一个数学观察，而不是定义算法;） – Cam 2010-03-16 00:18:54

如果你添加一个结构化的伪代码，我会很感激。我想你可能是在正确的轨道上，但我没有跟着你100％。 – 2010-03-16 00:44:11

看起来你想要在列表中包含第一个和最后一个元素。

如果您想从您的N个项目列表中拉出X个项目，您的步长将为（N-1）/（X-1）。不管你想要什么，只要你拔出每一个。

来源

2010-03-16 00:09:39 John

均匀地从数组中选择N个元素

回答

相关问题