Quel est le meilleur moyen de randomiser un ordre de tableau en PHP sans utiliser la fonction shuffle ()?

Question

On m'a posé cette question lors d'un entretien d'embauche. L'intervieweur et moi-même n'étions pas d'accord sur la réponse correcte. Je me demande si quelqu'un a des données à ce sujet.

Mise à jour: J'aurais dû mentionner que l'utilisation de shuffle () était formellement interdite ... désolé.

Answer 1

Vous pouvez utiliser le lecture aléatoire Fisher-Yates .

Answer 2

shuffle($arr);

:

modifier: je devrais préciser ... ma définition de "mieux" implique non seulement l'efficacité des algorithmes, mais aussi la lisibilité et la maintenabilité du code. Utiliser des fonctions de bibliothèque standard signifie conserver moins de code et lire beaucoup moins. Au-delà de cela, vous pouvez vous lancer dans des débats d'une année avec des professeurs de doctorat sur le meilleur "vrai hasard". donc quelqu'un sera toujours en désaccord avec vous sur les questions de randomisation.

Answer 3

Eh bien voici la solution que j'ai trouvée:

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

Et voici sa solution:

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

J’ai mené une série d’essais sur les deux méthodes (chaque fois 1 000 000 essais) et la différence de vitesse était négligeable. Cependant, après avoir vérifié le caractère aléatoire des résultats, j'ai été surpris de voir à quel point les distributions étaient différentes. Voici mes résultats:

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

Comme vous pouvez le constater, la première méthode fournit une distribution presque parfaite indiquant qu'elle est plus ou moins véritablement aléatoire, tandis que la seconde méthode est omniprésente.

Answer 4

Il vous teste probablement sur une erreur relativement courante commise par la plupart des gens lors de l’implémentation d’un algorithme de mélange (c’était également au centre d’un controverse sur un site de poker en ligne quelques années auparavant

Manière incorrecte de mélanger:

pour (i est 1 à n)   Échange i avec une position aléatoire entre 1 et n

Manière correcte de mélanger:

pour (i est 1 à n)   Échange i avec une position aléatoire entre i et n

Représentez graphiquement la distribution de probabilité pour ces cas et vous comprendrez pourquoi la première solution est incorrecte.

Answer 5

Le " correct " manière est assez vague. Le mieux (le plus rapide / le plus facile / le plus élégant) pour trier un tableau serait d’utiliser simplement la fonction intégrée shuffle ().

Answer 6

PHP a une fonction intégrée - > mélanger (). Je dirais que cela devrait faire ce que vous voulez, mais ce sera probablement autre chose que totalement «aléatoire».

Vérifiez http://computer.howstuffworks.com/question697.htm pour un peu description de la raison pour laquelle il est très très difficile d’obtenir un calcul aléatoire complet.

Answer 7

Réponse courte: La fonction array_rand () de PHP

Etant donné que l'utilisation de la fonction shuffle est interdite, j'utiliserais $ keys = array_rand ($ myArray, count ($ myArray)) pour renvoyer un tableau des clés à partir de $ myArray dans un ordre aléatoire. À partir de là, il devrait être simple de les réassembler dans un nouveau tableau randomisé. Quelque chose comme:

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

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