在 PHP 中不使用 shuffle() 函数随机化数组顺序的最佳方法是什么？

StackOverflow https://stackoverflow.com/questions/65970

  •  09-06-2019
  •  | 
  •  

题

我在面试时被问到这个问题。我和面试官对于正确答案的看法存在分歧。我想知道是否有人有这方面的数据。

更新：我应该提到的是严格禁止使用 shuffle()...对不起。

有帮助吗？

解决方案

你可以使用 费舍尔-耶茨洗牌.

其他提示

shuffle($arr);

:)

编辑：我应该澄清一下...我对最佳的定义不仅涉及算法效率，还涉及代码的可读性和可维护性。使用标准库函数意味着维护更少的代码并且阅读更少。除此之外，你可以与博士教授就最好的“真正的随机”函数进行长达一年的辩论，所以有人总是会在随机化问题上不同意你的观点。

这是我想出的解决方案：

function randomize_array_1($array_to_randomize) {
    $new_array = array();
    while (count($array_to_randomize) > 0) {
        $rand_num = rand(0, count($array_to_randomize)-1);
        $extracted = array_splice($array_to_randomize, $rand_num, 1);
        $new_array[] = $extracted[0];
    }
    return $new_array;
}

这是他的解决方案：

function randomize_array_2($array_to_randomize) {
    usort($array_to_randomize, "rand_sort");
    return $array_to_randomize;
}
function rand_sort($a, $b) {
    return rand(-1, 1);
}

我对这两种方法进行了一系列试验（每种方法尝试 1,000,000 次），速度差异可以忽略不计。然而，在检查结果的实际随机性后，我对分布的差异感到惊讶。这是我的结果：

randomize_array_1:
    [2, 3, 1] => 166855
    [2, 1, 3] => 166692
    [1, 2, 3] => 166690
    [3, 1, 2] => 166396
    [3, 2, 1] => 166629
    [1, 3, 2] => 166738

randomize_array_2:
    [1, 3, 2] => 147781
    [3, 1, 2] => 73972
    [3, 2, 1] => 445004
    [1, 2, 3] => 259406
    [2, 3, 1] => 49222
    [2, 1, 3] => 24615

正如您所看到的，第一种方法提供了几乎完美的分布，表明它或多或少是真正随机的，而第二种方法则到处都是。

他可能正在测试你大多数人在实现洗牌算法时犯的一个相对常见的错误（这实际上也是一个洗牌算法的核心） 争议 涉及几年前的在线扑克网站）

错误的洗牌方式：

for (i is 1 to n) Swap i with random position between 1 and n

正确的洗牌方法：

for (i is 1 to n) Swap i with random position between i and n

绘制出这些情况的概率分布，很容易看出为什么第一个解决方案是不正确的。

“正确”的方式相当模糊。对数组进行排序的最佳（最快/最简单/最优雅）是仅使用内置的 shuffle() 函数。

PHP 有一个内置函数 --> shuffle() 。我想说，这应该做你喜欢做的事，但它很可能不是完全“随机”的。

查看 http://computer.howstuffworks.com/question697.htm 稍微描述一下为什么从计算机中获得完全的随机性非常非常困难。

简短回答：PHP 的 array_rand() 功能

鉴于禁止使用 shuffle 函数，我会使用 $keys = array_rand($myArray, count($myArray)) 返回一个键数组 $myArray 以随机顺序。从那里开始，将它们重新组装成一个随机的新数组应该很简单。就像是： 

$keys = array_rand($myArray, count($myArray));
$newArray = array();

foreach ($keys as $key) {
$newArray[$key] = $myArray[$key];
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top