Analyse approfondie des compétences de l'algorithme de brassage aléatoire javascript

Analyse approfondie des compétences de l'algorithme de brassage aléatoire javascript_javascript

WBOY

Libérer： 2016-05-16 16:45:32

original

1659 Les gens l'ont consulté

L'algorithme de brassage est un problème aléatoire courant que nous rencontrons souvent lors des jeux et du tri aléatoire. Cela peut être résumé comme ceci : obtenez un tableau de séquences aléatoires de tous les nombres naturels dans M.

En recherchant "Shuffling Algorithm" sur Baidu, le premier résultat est "Baidu Library-Shuffling Algorithm". Après avoir analysé le contenu, de nombreux contenus peuvent facilement induire les autres en erreur, y compris l'utilisation de listes chaînées au lieu de tableaux à la fin. . Il ne s'agit également que d'une optimisation limitée (les listes chaînées introduisent également une perte d'efficacité en lecture).

La première méthode de cet article peut être simplement décrite comme : piochez des cartes au hasard et placez-les dans un autre groupe ; si vous piochez une carte vide, répétez le tirage.
"Si vous piochez une carte vide, piochez-la à nouveau." Cela augmentera les chances de piocher une carte vide plus tard, ce qui est évidemment déraisonnable.
Il peut être optimisé en une seule étape : une fois les cartes supprimées, les cartes originales seront réduites. (Au lieu de laisser une carte vide)
Le code est le suivant :

Copiez le codeLe code est le suivant :

fonction shuffle_pick_1(m) //Shuffle//Méthode de dessin de cartes
{
//Générer m cartes
var arr = new Array(m);
pour (var i=0 ; i arr[i] = i;
}

//Piochez une carte à chaque fois et mettez-la dans une autre pile. Étant donné que vous devez extraire des éléments du tableau et avancer d'un élément tous les éléments suivants, cela prend beaucoup de temps.
var arr2 = new Array();
for (var i=m; i>0; i--) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr.splice(rnd,1);
}
return arr2;
}

C'est aussi évidemment problématique, car si le tableau est très grand, la suppression d'un élément au milieu fera avancer la file d'attente suivante, ce qui est une action très longue.
Rappel "Pourquoi veut-on supprimer cet élément ?" Le but n'est pas de produire des cartes vides.
En plus de supprimer cet élément, existe-t-il d'autres moyens pour nous de supprimer les cartes vides ?
----Oui, on vient de mettre la dernière carte non tirée en position tirée.
Donc, on peut optimiser cette idée comme ceci :

Copier le code Le code est le suivant :

function shuffle_pick(m) //shuffle/ /pump Carte d'optimisation de carte
{
// Générer m cartes
var arr = new Array(m);
for (var i=0; i arr [je] = je;
}

//Piochez une carte à chaque fois et mettez-la dans une autre pile. Placez la dernière carte non tirée sur le siège vide.
var arr2 = new Array();
for (var i=m; i>0;) {
var rnd = Math.floor(Math.random()*i);
arr2 .push(arr[rnd]);
arr[rnd] = arr[--i];
}
return arr2;
}

Sauf pour le dessin cartes Quant à l'idée, on peut aussi utiliser l'idée de changer de carte.
"Baidu Wenku - Shuffling Algorithm" mentionne une idée de changement de carte : "Échangez aléatoirement deux positions pour un total de n fois. Plus n est grand, plus il est proche du hasard."
Cette approche est erronée. Même si n est très grand (par exemple, 10 cartes, 10 échanges), il existe toujours une forte possibilité que "certaines cartes n'aient pas changé de position du tout".
En suivant cette idée, faites juste un petit ajustement : changez la position de la i-ème carte avec n'importe quelle autre carte, puis terminez le tour.
Le code est le suivant :

Copier le code Le code est le suivant :

function shuffle_swap(m) //shuffle/ /swap Card méthode
{
// Générer m cartes
var arr = new Array(m);
for (var i=0; i arr[ je ] = je;
}

//Échangez la i-ème carte avec n'importe quelle carte après un tour
pour (var i=0; i var rnd = Math.floor( Math.random()* (i 1)),
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}

En plus de l'idée de piocher et d'échanger des cartes, on peut aussi utiliser l'idée d'insérer des cartes : il y a d'abord une carte, la deuxième carte a deux positions qui peuvent être insérées aléatoirement (avant ou après la première carte), et la troisième Il y a trois positions pour qu'une carte soit insérée aléatoirement (au dos, ou en première place, ou en deuxième place), et ainsi de suite
Le code est le suivant :

Copier le code Le code est le suivant :

fonction shuffle_insert_1(m) //shuffle/ /insert Card method 
{
 //Génère à chaque fois la plus grande carte et insère-la devant une carte aléatoire. Étant donné que vous devez insérer des éléments dans le tableau et repousser tous les éléments suivants d'une position, cela prend beaucoup de temps. 
 var arr = [0];
 for (var i=1; i arr.splice(Math.floor(Math.random()*(i 1)), 0,i);
 }
 retour arr;
}

Le code ci-dessus aura également quelques problèmes : à mesure que le nombre de cartes augmente, il devient de plus en plus difficile d'insérer des cartes, car l'insertion de cartes entraînera le refoulement de nombreuses cartes suivantes.
Bien sûr, on peut aussi l'optimiser de manière appropriée : il y a n-1 cartes en premier, la n-ème carte est placée à la fin, puis elle échange ses positions avec n'importe quelle carte.
Le code est le suivant :

Copier le code Le code est le suivant :

function shuffle_insert(m) //shuffle/ /insert La version optimisée de la méthode des cartes peut être prouvée par induction mathématique que ce type de brassage est uniforme. 
{
 //Générez à chaque fois la carte la plus élevée et échangez les places avec une carte aléatoire
 var arr = new Array(m);
 arr[0] = 0;
 for (var je=1; je var rnd = Math.floor(Math.random()*(i 1));
 arr[i] = arr[rnd] ;
 arr [rnd] = i;
 }
 return arr;
}

D'accord, l'ensemble du code est le suivant. Les étudiants intéressés peuvent l'essayer sur leurs propres machines pour voir leur efficacité d'exécution respective et si le résultat final est théoriquement aléatoire.

Copier le code Le code est le suivant :

< title>JK：algorithme de brassage javascript