L'algorithme de mélange est un problème aléatoire commun que nous rencontrons lors de la lecture de jeux et du tri au hasard. Il peut être abstrait comme ceci: obtenez un tableau de commande aléatoire de tous les nombres naturels dans M.
À la recherche de "algorithme de remaniement" sur Baidu, le premier résultat a été "Baidu Library - Reshukle Algorithme". Après avoir scanné le contenu, de nombreux contenus sont faciles à induire en erreur les autres, notamment en utilisant des listes liées pour remplacer les tableaux à la fin, ce qui n'est qu'une optimisation limitée (les listes de liens introduisent également la perte d'efficacité de lecture).
La première méthode de cet article peut être simplement décrite comme: dessiner au hasard et les mettre dans un autre groupe; Dessinez-les à nouveau, dessinez-les à plusieurs reprises lorsque vous dessinez les cartes vides.
"Dessiner les cartes après les dessin à nouveau" mènera aux chances croissantes de tirer les cartes plus tard, ce qui est évidemment déraisonnable.
Une étape peut être optimisée: une fois les cartes tirées, les cartes d'origine deviennent moins. (plutôt que de laisser des cartes vides)
Le code est le suivant:
La copie de code est la suivante:
fonction shuffle_pick_1 (m) //
{
// générer des cartes M
var arr = nouveau tableau (m);
pour (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Dessinez une carte à la fois et placez-la dans une autre pile. Parce que vous devez extraire des éléments du tableau et tirer tous les éléments suivants vers l'avant un par un, il prend du temps.
var arr2 = new Array ();
pour (var i = m; i> 0; i--) {
var rnd = math.floor (math.random () * i);
arr2.push (arr [rnd]);
Arr.splice (RND, 1);
}
retour arr2;
}
Ceci est également évidemment problématique, car si le tableau est important, la suppression d'un certain élément au milieu fera que la file d'attente fera un pas en avant, ce qui est une action très longue.
Rappelons le but de "Pourquoi supprimons-nous cet élément?" est d'éviter les cartes vides.
En plus de supprimer cet élément, avons-nous d'autres moyens de supprimer les cartes vides?
---- Oui, nous avons juste besoin de mettre la dernière carte non reprochée en position de tirage.
Ainsi, nous pouvons optimiser cette idée comme suit:
La copie de code est la suivante:
Function Shuffle_Pick (M) // Fermez // Méthode de dessin de la carte pour optimiser la carte
{
// générer des cartes M
var arr = nouveau tableau (m);
pour (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Dessinez une carte à la fois et placez-la dans une autre pile. Mettez la dernière carte non réractée sur le siège ouvert.
var arr2 = new Array ();
pour (var i = m; i> 0;) {
var rnd = math.floor (math.random () * i);
arr2.push (arr [rnd]);
arr [rnd] = arr [- i];
}
retour arr2;
}
En plus de l'idée de dessiner des cartes, nous pouvons également utiliser l'idée de changer de cartes.
"L'algorithme de shut de Baidu Wenku" mentionne une idée de changement de carte: "Communiquez deux positions au hasard et échangez-les au total. Plus le 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 commutateurs), il y a toujours une forte possibilité que "certaines cartes ne changent pas du tout des positions".
Suivez cette idée et effectuez un petit ajustement: modifiez la I-Tth Carte avec n'importe quelle carte, et changez-la simplement pour un tour.
Le code est le suivant:
La copie de code est la suivante:
fonction shuffle_swap (m) // shush // méthode de changement de carte
{
// générer des cartes M
var arr = nouveau tableau (m);
pour (var i = 0; i <m; i ++) {
arr [i] = i;
}
// La carte I-TH est utilisée pour changer les sièges et vous pouvez le changer pour un tour
pour (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random () * (i + 1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
retour arr;
}
En plus de l'idée de dessiner et de changer de cartes, nous pouvons également utiliser l'idée d'insérer des cartes: d'abord il y a une carte, la deuxième carte a deux positions à insérer au hasard (avant ou derrière la première carte), la troisième carte a trois positions à insérer au hasard (placées derrière ou insérées dans la première position, ou insérée dans la deuxième position), et ainsi de suite
Le code est le suivant:
La copie de code est la suivante:
fonction shuffle_insert_1 (m) // shunt // méthode d'insertion de carte
{
// À chaque fois, la plus grande carte est générée et insérée devant une carte aléatoire. Parce que vous devez insérer des éléments dans le tableau et presser tous les éléments suivants un par un, il prend du temps.
var arr = [0];
pour (var i = 1; i <m; 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 des cartes mènera à de nombreuses cartes qui suivent un pas en arrière.
Bien sûr, nous pouvons également optimiser de manière appropriée: il y a d'abord une carte N-1, la carte N-TH est placée à la fin, puis d'échanger des positions avec n'importe quelle carte.
Le code est le suivant:
La copie de code est la suivante:
fonction shuffle_insert (m) // shush // La version optimisée de la méthode d'insertion de la carte peut être prouvée par induction mathématique que ce remaniement est uniforme.
{
// chaque fois génère la plus grande carte et échange des positions avec une carte aléatoire
var arr = nouveau tableau (m);
arr [0] = 0;
pour (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random () * (i + 1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
retour arr;
}
Ok, tous les codes sont les suivants. Les étudiants intéressés peuvent les essayer sur leur propre machine pour voir si leur efficacité d'exécution respective et si le résultat final est théoriquement aléatoire.
La copie de code est la suivante:
<html>
<adal>
<meta http-equiv = "content-type" content = "text / html; charset = gb2312">
<Title> JK: algorithme de mélange JavaScript </TITAL>
</ head>
<body>
<script type = "text / javascript">
fonction shuffle_pick_1 (m) //
{
// générer des cartes M
var arr = nouveau tableau (m);
pour (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Dessinez une carte à la fois et placez-la dans une autre pile. Parce que vous devez extraire des éléments du tableau et tirer tous les éléments suivants vers l'avant un par un, il prend du temps.
var arr2 = new Array ();
pour (var i = m; i> 0; i--) {
var rnd = math.floor (math.random () * i);
arr2.push (arr [rnd]);
Arr.splice (RND, 1);
}
retour arr2;
}
Function Shuffle_Pick (M) // Fermez // Méthode de dessin de la carte pour optimiser la carte
{
// générer des cartes M
var arr = nouveau tableau (m);
pour (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Dessinez une carte à la fois et placez-la dans une autre pile. Mettez la dernière carte non réractée sur le siège ouvert.
var arr2 = new Array ();
pour (var i = m; i> 0;) {
var rnd = math.floor (math.random () * i);
arr2.push (arr [rnd]);
arr [rnd] = arr [- i];
}
retour arr2;
}
fonction shuffle_swap (m) // shush // méthode de changement de carte
{
// générer des cartes M
var arr = nouveau tableau (m);
pour (var i = 0; i <m; i ++) {
arr [i] = i;
}
// La carte I-TH est utilisée pour changer les sièges et vous pouvez le changer pour un tour
pour (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random () * (i + 1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
retour arr;
}
fonction shuffle_insert_1 (m) // shunt // méthode d'insertion de carte
{
// À chaque fois, la plus grande carte est générée et insérée devant une carte aléatoire. Parce que vous devez insérer des éléments dans le tableau et presser tous les éléments suivants un par un, il prend du temps.
var arr = [0];
pour (var i = 1; i <m; i ++) {
arr.splice (math.floor (math.random () * (i + 1)), 0, i);
}
retour arr;
}
fonction shuffle_insert (m) // shush // La version optimisée de la méthode d'insertion de la carte peut être prouvée par induction mathématique que ce remaniement est uniforme.
{
// chaque fois génère la plus grande carte et échange des positions avec une carte aléatoire
var arr = nouveau tableau (m);
arr [0] = 0;
pour (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random () * (i + 1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
retour arr;
}
// alerte (shuffle_pick (10))
var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
FuncNames = ["Draw Card", "Draw Card Optimization", "Card Change", "Card Insert", "Card Insérer Optimization"]
M = 10000,
Times = [];
pour (var i = 0; i <funcs.length; i ++) {
var d0 = new Date ();
funcs [i] (m);
funcNames [i] = (new Date () - d0) + '/ t' + funcNames [i];
}
alert (funcnames.join ('/ n'));
</cript>
</docy>
</html>