在工作面试中有人问我这个问题。我和访调员不同意正确答案是什么。我想知道是否有人对此有任何数据。

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

解决方案

回答

shuffle($arr);

:)

编辑：我应该澄清...我对最佳的定义不仅涉及算法效率，还涉及代码的可读性和可维护性。使用标准的库函数意味着维护更少的代码，也需要更少的读取。除此之外，我们还可以与博士学位教授就最佳的"真正随机"功能进行为期一年的辩论，因此有人总是会在随机问题上与我们不同意。

回答

"正确"的方法非常模糊。最好(最快/最简单/最优雅)对数组进行排序的方法是仅使用内置的shuffle()函数。

回答

PHP具有内置功能-> shuffle()。我想说这应该做我们想做的，但是很可能除了完全"随机"之外，什么都做。

请访问http://computer.howstuffworks.com/question697.htm，以获取有关为什么很难从计算机获得完全随机性的简短描述。

回答

我们可以使用Fisher-Yates随机播放。

回答

简短的答案：PHP的array_rand()函数

鉴于禁止使用随机播放功能，我将使用$ keys = array_rand($ myArray，count($ myArray))以随机顺序从$ myArray中返回键数组。从那里开始，将它们重新组装成已经随机化的新数组应该很简单。就像是：

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

foreach ($keys as $key) {
$newArray[$key] = $myArray[$key];
}

回答

他可能正在测试我们在大多数人实施改组算法时犯的一个相对普遍的错误(这实际上也是几年前涉及在线扑克网站的争议的中心)

不正确的随机播放方式：

对于(i是1到n) 以1到n之间的随机位置交换i

正确的洗牌方式：

对于(i是1到n) 以i和n之间的随机位置交换i

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

回答

好吧，这是我想出的解决方案：

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

如我们所见，第一种方法提供了几乎完美的分布，表明它实际上是随机的，而第二种方法则无处不在。