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

Question

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

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

Answer 1

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

Answer 2

shuffle($arr);

:)

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

Answer 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

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

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

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

Answer 6

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

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

Answer 7

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