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

Question

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

12

我需要从一个数组中均匀选择n个元素。最好的解释方式是通过示例。假设我有一个数组 [0,1,2,3,4]，我需要选择3个数字 0、2、4。当然，如果数组长度小于等于n，则只需返回整个数组。我相信有一种定义好的算法可以解决这个问题，一直在尝试搜索，查看了《算法导论》，但没有找到满足我的需要的任何内容（可能是我漏看了）。我遇到的问题是无法找到一种方法来扩展到任何数组 [p..q]，选择N个均匀元素。注意：我不能仅选择上述示例中的偶数元素。几个其他的例子：array [0,1,2], 2个元素:0、2；array [0,1,2,3,4,5,6,7], 5个元素:0、2、3或4，5、7。是的，我希望始终包括第一个和最后一个元素。

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

?>

你可以实现一个迭代器，但我不需要那么麻烦。

- Jean Paul Galea

你需要选择哪些数字？请更具体地描述你的模式。 - Kevin Crowell

我认为你需要更多的例子，因为我仍然不明白你想做什么。那么对于更长的数组和不同数量的元素选择呢？ - Dean Harding

如果我理解得正确，OP想要选择一些数组元素，其索引遵循某种规律。我认为Rex Kerr的答案可能更好地解释了这里所问的问题。 - bta

5个回答

3

假设你需要的元素数量为n+1，已经限制在数组长度内。

那么你需要取到的元素下标为从数组结尾开始往前数的第0/n、1/n、...、n/n个位置。

假设数组长度为m+1，则你需要的下标为round(m*i/n)（除法采用浮点数）。

- Rex Kerr

这是不正确的。使用长度为m的0索引数组，最后一个索引应该是m-1而不是m，因此索引应该是round((m-1)*i/n)（浮点数除法，如所述）。 - Clueless

如果您能添加结构化的伪代码，我会非常感激。我认为您可能走在正确的道路上，但我并没有完全理解您的意思。 - Jean Paul Galea

@clueless：糟糕，数组长度已修正为m+1。这就是我试图输入的内容（与n+1一样）。 - Rex Kerr

1

你的步长是（ArraySize-1）/（N-1）。
只需将步长添加到浮点累加器中，并四舍五入累加器以获取数组索引。重复此过程，直到累加器>数组大小。

- AShelly

1

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

如果你想从N个项目的列表中提取X个项目，你的步长将是(N-1)/(X-1)。只要在提取每个项目时进行四舍五入即可。

- John

1

根据 @Rex 的回答。伪代码！或者有些人甚至会说这是 JS

    /// Selects |evenly spaced| elements from any given array. Handles all the edge cases.
    function select(array: [Int], selectionCount: Int) {

      let iterationCount = array.length - 1;           // Number of iterations
      let expectedToBeSelected = selectionCount - 1;   // Number of elements to be selected
      let resultsArray: [Int] = [];                    // Result Array

      if (selectionCount < 1 || selectionCount > array.length) {
        console.log("Invalid selection count!");
        return resultsArray;
      }
      var i;
      for (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;
    }

- Ajo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cam · Accepted Answer

伪代码：

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）