Qual é a melhor maneira de randomizar a ordem de um array em PHP sem usar a função shuffle()?

Question

Essa pergunta me foi feita em uma entrevista de emprego.O entrevistador e eu discordamos sobre qual era a resposta correta.Gostaria de saber se alguém tem algum dado sobre isso.

Atualizar:Eu deveria ter mencionado que o uso de shuffle() era estritamente proibido...desculpe.

Answer 1

Você poderia usar o Embaralhamento Fisher-Yates.

Answer 2

shuffle($arr);

:)

editar:Eu deveria esclarecer...minha definição de melhor envolve não apenas a eficiência do algoritmo, mas também a legibilidade e a manutenção do código.Usar funções de biblioteca padrão significa manter menos código e ler muito menos também.Além disso, você pode entrar em debates de um ano com professores de doutorado sobre a melhor função "verdadeiramente aleatória", para que alguém sempre discorde de você em questões de randomização.

Answer 3

Bem, aqui está a solução que encontrei:

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

E aqui está a solução dele:

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

Fiz vários testes em ambos os métodos (tentando 1.000.000 de vezes cada um) e a diferença de velocidade foi insignificante.No entanto, ao verificar a real aleatoriedade dos resultados, fiquei surpreso com o quão diferentes eram as distribuições.Aqui estão meus resultados:

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

Como você pode ver, o primeiro método fornece uma distribuição quase perfeita, indicando que está sendo mais ou menos verdadeiramente aleatório, enquanto o segundo método está em todos os lugares.

Answer 4

Ele provavelmente está testando você sobre um erro relativamente comum que a maioria das pessoas comete ao implementar um algoritmo de embaralhamento (isso também estava no centro de uma controvérsia envolvendo um site de pôquer online há alguns anos atrás)

Maneira incorreta de embaralhar:

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

Maneira correta de embaralhar:

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

Faça um gráfico da distribuição de probabilidade para esses casos e será fácil ver por que a primeira solução está incorreta.

Answer 5

A maneira "correta" é bastante vaga.O melhor (mais rápido/mais fácil/mais elegante) para classificar um array seria apenas usar a função shuffle() integrada.

Answer 6

PHP tem uma função integrada -> shuffle() .Eu diria que isso deveria fazer o que você quiser, mas provavelmente será tudo menos totalmente 'aleatório'.

Verificar http://computer.howstuffworks.com/question697.htm para obter uma pequena descrição de por que é muito, muito difícil obter a aleatoriedade completa de um computador.

Answer 7

Resposta curta:PHP array_rand() função

Dado que o uso da função shuffle é proibido, eu usaria $keys = array_rand($myArray, count($myArray)) para retornar uma matriz das chaves de $myArray em ordem aleatória.A partir daí, deve ser simples reagrupá-los em um novo array que foi randomizado.Algo como:

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

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