3

我在一次工作面试中被问到这个问题。面试官和我不同意正确答案是什么。我想知道是否有人有这方面的任何数据。

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

4

7 回答 7

4 
shuffle($arr);

:)

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

于 2008-09-15T19:30:10.887 回答
3

那么这是我想出的解决方案：

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

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

于 2008-09-15T20:49:34.190 回答
2

您可以使用Fisher-Yates shuffle。

于 2008-09-15T20:32:26.290 回答
1

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

不正确的洗牌方式：

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

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

于 2008-09-15T20:44:30.427 回答
0

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

于 2008-09-15T19:37:15.160 回答
0

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

查看http://computer.howstuffworks.com/question697.htm了解为什么它非常非常难以从计算机中获得完全随机性。

于 2008-09-15T20:08:21.780 回答
0

简答：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];
}
于 2008-09-15T20:35:49.793 回答