3

我有一个完全填充的值数组，我想从这个数组中任意删除元素，并在远端删除更多元素。

例如，给定输入（其中 . 表示填充索引）

............................................

我想要类似的东西

....... . ...  .. .  .  ..    .          .

我的第一个想法是计算元素，然后遍历数组，在当前索引和数组总大小之间生成一个随机数，例如：

if ( mt_rand( 0, $total ) > $total - $current_index ) 
    //remove this element

但是，由于这需要在每次循环循环时生成一个随机数，因此变得非常困难。

有没有更好的方法来做到这一点？

4

3 回答 3

2

这很可能不是最好/最有效的方法，但这是我能想到的最好的方法，它确实有效。

注意键盘示例需要很长时间才能执行，但这是因为我在末尾添加了漂亮的打印循环，因此您可以看到它明显有效。如果删除内部循环，执行时间会下降到可接受的水平。

<?php

  $array = range(0, 99);

  for ($i = 0, $count = count($array); $i < $count; $i++) {

    // Get array keys
    $keys = array_keys($array);

    // Get a random number between 0 and count($keys) - 1
    $rand = mt_rand(0, count($keys) - 1);

    // Cut $rand elements off the beginning of the keys
    $keys = array_slice($keys, $rand);

    // Unset a random key from the remaining keys
    unset($array[$keys[array_rand($keys)]]);

  }
于 2012-05-29T14:48:36.037 回答
2

一种简单的方法是为每个条目翻转一个加权硬币，硬币翻转在最后的权重更大。例如，如果数组大小为 n，则对于每个条目，您可以从0to 中选择一个随机数，n-1并且仅当索引小于或等于随机数时才保留该值。（也就是说，保留每个条目的概率1 - index/total。）这有一个很好的优势，如果你无论如何都要压缩你的数组，并且你正在使用一个足够好但有效的随机数生成器（可能是一个简单的整数散列一个随机数），内存访问会相当快。

另一方面，如果您只是删除了一些项目并且没有重新排列数组，您可以使用某种加权随机数生成器，它更经常选择接近索引末尾的数字。例如，如果您有一个随机数生成器生成 [0,1] 值的浮点数（封闭或开放边界不太可能），请考虑获取这样的随机浮点数r并将其平方。这将倾向于使用较低的值。您可以通过翻转它来解决此问题：1-r^2. 当然，您需要它在 to 的索引范围内0，n - 1所以取floor(n * (1 - r^2))并向下舍n入 to n-1。

这两种技术实际上有无数种变化。

于 2012-05-29T14:05:34.640 回答
1

这个方法不是随机的——它通过你定义一个函数和它的逆来工作。不同的函数，具有不同的常数系数，会有不同的分布特征。

结果非常类似于模式，正如将连续函数映射到数组等离散结构时所预期的那样。

这是使用二次函数的示例。你可以尝试改变常数。

演示：http ://codepad.org/ojU3s9xM

#as in y = x^2 / 7;
function y($x) {
    return $x * $x / 7;
}
function x($y) {
    return 7 * sqrt($y);
}

$theArray = range(0,100);
$size = count($theArray);

//use func inverse to find the max value we can input to $y() without going out of array bounds
$maximumX = x($size);
for ($i=0; $i<$maximumX; $i++) {
    $index = (int) y($i);

    //unset the index if it still exists, else, the next greatest index
    while (!isset($theArray[$index]) && $index < $size) {
        $index++;
    }

    unset($theArray[$index]);
}




for ($i=0; $i<$size; $i++) {
    printf("[%-3s]", isset($theArray[$i]) ? $theArray[$i] : '');
}
于 2012-05-29T15:22:55.870 回答