Inscription / Connexion Nouveau Sujet
Mélange aléatoire
Bonjour,
Lors d'un projet informatique (c'est la partie math qui m'intéresse donc je poste ici) un élève avait besoin de mélanger des données, on pourra dire mélanger un jeu de cartes toutes distinctes. Il a eu l'idée d'utiliser l'algorithme suivant:
Intervertir deux cartes. Recommencer 1000 fois. Le choix des cartes à intervertir se faisait via une loi uniforme pour la première, même chose pour la deuxième jusqu'à ce qu'elle soit différente de la première. Je lui ai expliqué que son mélange ne pouvait pas arriver à toutes les possibilités : Nombre pair de transposition.
Il m'a dit alors qu'il pouvait choisir via une loi uniforme 1000 ou 1001 répétitions. Je lui ai dit: et si tu ne tenais pas compte du fait que la deuxième carte choisie doit être différente de la première en conservant 1000 répétitions?
Au final nous avons deux choix. Sont elles équivalentes? Amène t elles à tous les mélanges et de manière equiprobables?
Bonsoir,
en fait on peut obtenir les permutations paire en tirant deux fois la même transposition.
Le tirage n'est pas uniforme dans l'ensemble des permutations.
Un exemple simple avec 3 cartes.
Il y a alors trois transpositions et, si on en fait n à la suite, on a 3n tirages possibles équiprobables or 3n n'est pas un multiple de 3!=6.
Le problème le plus important et qui fait que l'on a pas toutes les permutation vient du générateur aléatoire.
Si il y a plus de 40 cartes il faut qu'il ait un cycle plus grand que 2165
Merci Verdurin, le problème d'equiprobabilité, je l'avais mis ici sans y avoir réfléchi. C'était surtout le fait que tous les tirages soient atteignable qui m'intéressaient à l'époque. Du coup, comment mélanger n cartes algorithmiquement afin d'avoir tous les tirages possibles et de manière equiprobable? On a à disposition un générateur aléatoire de nombre suivant une loi uniforme ?
Pour ton problème l'algorithme classique ( celui que je connais ) est :
-- on prend une carte au hasard parmi les n dont on dispose et on l'échange avec la dernière carte ( qui peut-être échangée avec elle même )
-- on recommence avec les n-1 cartes restantes.
Avec un générateur aléatoire parfait ça marche sans problème.
PS : en relisant mon premier message je viens de voir que j'ai écris « permutation paire » à la place de « permutation impaire ».
Oui j'avais rectifié impaire, c'est pour cela que j'ai dit à l'élève de ne pas forcer que la deuxième carte soir différente.
Bien vu pour ton algo.
En fait j'ai l'impression cet algorithme montre qu'en faisant 2(n-1) transpositions différentes de l'identité on peut obtenir toutes les permutations d'un ensemble à n éléments.
Et il me semble que, si elles sont choisies au hasard parmi les n(n-1)/2 possibilités, les permutations ne seront pas équiprobables.
Bonsoir jarod128.
À part algorithme j'ai, dans l'ensemble, écris n'importe quoi.
Avec sous-jacente la croyance qu'un entier assez grand est à la fois pair et impair.
J'espère que tu voudras bien m'excuser.
Annuler
connectez vous