¿Cuál es la mejor manera para aleatorizar una matriz de orden en PHP sin utilizar la reproducción aleatoria() la función?

Question

Yo era esta pregunta en una entrevista de trabajo.El entrevistador y yo no estaba de acuerdo en lo que la respuesta correcta era.Me pregunto si alguien tiene alguna información sobre este tema.

Actualización:Yo debería haber mencionado que el uso de shuffle() estaba estrictamente prohibido...lo siento.

Answer 1

Usted podría utilizar la Fisher-Yates shuffle.

Answer 2

shuffle($arr);

:)

editar:Debo aclarar...mi definición de la mejor implica no solo algoritmo de eficiencia, pero la legibilidad del código y la facilidad de mantenimiento así.El uso de la biblioteca estándar de funciones de mantenimiento de la menos código y leyendo mucho menos demasiado.Más allá de eso, usted puede conseguir en un año debates con los profesores doctores acerca de la mejor "true random" de la función, de modo que alguien siempre va a estar en desacuerdo con usted en la aleatorización de las preguntas.

Answer 3

Bueno, aquí está la solución que se me ocurrió:

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

Y aquí está su solución:

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

Me encontré con un montón de pruebas en ambos métodos (tratando cada 1.000.000 de veces) y la diferencia de velocidad era insignificante.Sin embargo, al comprobar la aleatoriedad de los resultados me sorprendieron en cómo los diferentes distribuciones fueron.He aquí mis 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 se puede ver, el primer método proporciona una casi perfecta distribución que indica que se está más o menos realmente aleatorios, mientras que el segundo método es por todo el lugar.

Answer 4

Probablemente la prueba en un relativamente error más común que la gente comete al aplicar un algoritmo de barajado (este fue, de hecho, en el centro de un la controversia involucra a un sitio de poker en línea un par de años atrás)

De modo incorrecto a shuffle:

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

Forma correcta de mezclar:

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

Gráfico de la distribución de probabilidad para estos casos y es fácil ver por qué la primera solución es incorrecta.

Answer 5

La manera "correcta" es muy vago.El mejor (el más rápido / más fácil / más elegante) para ordenar una matriz sería utilizar el built-in shuffle() función.

Answer 6

PHP tiene una función integrada --> aleatorio() .Yo diría que debería hacer lo que te gusta, pero es probable que la mayoría va a ser cualquier cosa, pero totalmente "al azar".

Verificación http://computer.howstuffworks.com/question697.htm para una pequeña explicación de por qué su muy, muy difícil de conseguir completa aleatoriedad formar un equipo.

Answer 7

Respuesta Corta:PHP array_rand() la función

Dado que el uso de la función de reproducción aleatoria está prohibido, me gustaría utilizar $keys = array_rand($myArray, count($myArray)) para devolver una matriz de las claves de $myArray en orden aleatorio.Desde allí debe ser simple de volver a montar en una nueva matriz que ha sido al azar.Algo así como:

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

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