Каков наилучший способ рандомизировать порядок массива в PHP без использования функции shuffle ()?

Question

Мне задали этот вопрос на собеседовании. Интервьюер и я не согласились с тем, каков был правильный ответ. Мне интересно, есть ли у кого-нибудь данные по этому вопросу.

Обновление: я должен был упомянуть, что использование shuffle () было строго запрещено ... извините.

Answer 1

shuffle($arr);

:)

редактировать: я должен уточнить ... мое определение лучшего включает в себя не только эффективность алгоритма, но и читаемость кода и ремонтопригодность. Использование стандартных библиотечных функций означает сохранение меньшего количества кода и чтение намного меньше. Кроме того, вы можете участвовать в круглогодичных дебатах с профессорами PhD о лучшей «истинно случайной» функции, поэтому кто-то всегда будет с вами не согласен по вопросам рандомизации.

Answer 2

Ну вот решение, которое я придумал:

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

Я провел несколько испытаний по обоим методам (пытаясь каждый раз по 1000000 раз), и разница в скорости была незначительной. Однако, проверив фактическую случайность результатов, я был удивлен тем, насколько различными были распределения. Вот мои результаты:

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

Как видите, первый метод обеспечивает почти идеальное распределение, что указывает на то, что он более или менее действительно случайный, тогда как второй метод повсеместно.

Answer 3

Вы можете использовать shuffle Фишера-Йейтса .

Answer 4

Он, вероятно, тестирует вас на относительно распространенной ошибке, которую большинство людей допускают при реализации алгоритма тасования (это также было в центре спора с участием онлайн-покерного сайта несколько лет назад)

Неправильный способ перемешивания:

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

Составьте график распределения вероятностей для этих случаев, и легко понять, почему первое решение неверно.

Answer 5

Краткий ответ: 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];
}

Answer 6

PHP имеет встроенную функцию -> shuffle (). Я бы сказал, что должен делать то, что вам нравится, но, скорее всего, это будет совсем не случайно.

Проверьте http://computer.howstuffworks.com/question697.htm для небольшого описания того, почему очень, очень трудно получить полную случайность из компьютера.

Answer 7

«Правильный» путь довольно расплывчатый. Лучший (самый быстрый / самый простой / самый элегантный) для сортировки массива - просто использовать встроенную функцию shuffle ().