Discussion :

[cjacquel]

Bonjour,

J'ai un tableau ordonné:
0, 1, 2, 3, 4, 5

Comment générer le plus rapidement un tableau de ces chiffres mis aléatoirement :
4 3 5 2 0 1

Merci,
Christophe,

[Invité]

Bonjour, je pense qu'il te suffit de permuter deux éléments choisi aléatoirement "nombre d'élément du tableau"/2 fois.


Donc il faut tirer deux entiers appartenant à l'index du tableau et permuter les éléments aux deux index aléatoire max_element/2 fois

[tbc92]

Pour n éléments, faire n/2 permutations permet de bien mélanger, mais ce n'est pas aussi efficace qu'un tri aléatoire 'complet'.
Par exemple, à partir de 123456, un tri purement aléatoire peut donner 234561. Alors que faire 3 permutations ne peut pas donner ce résultat.
A priori, le plus économique, c'est de prendre 1 élément aléatoire, et le mettre en début de liste.
Et répéter l'opération n-1 fois. (n-1 en tout, ou, ne soyons pas radin, n fois en tout )
Après, selon le langage utilisé, selon je ne sais quel autre critère, selon la façon dont les données sont déplaçables dans une liste, il y a des variantes qui seront un peu plus rapides, ou un peu moins rapides.

[plaxtor]

Salut! Pour apporter un complément mathématique si tu veux que toutes tes permutations soient équiprobables tu ne peux pas appliquer la méthode de tbc92 je m'explique:
Si tu mélange de cette manière tu auras n^n issues équiprobables. Or le nombre de permutations (n!) ne divise pas n^n pour n>2 (car n-1 ne divise pas n) autrement dit toutes les permutations n'auront pas la même probabilité, ce n'est pas un 'bon' mélange donc. Si tu veux faire ça il faut que tu permutes le premier élément avec n'importe quel élément de la liste, le deuxième avec n'importe quel élément de la n-1 dernier termes (tous sauf le 1er donc) ... et l'avant dernier avec lui même ou dernier. Et là ça sera totalement aléatoire.

Mais je ne pense pas que ce soit la méthode la plus efficace, car le plus gourmand en temps, c'est de générer un nombre aléatoire. Personnellement je n'en génèrerai qu'un seul, dans [[0, n! - 1]] qui représenterait une permutation quelconque. Ensuite tu décompose ce nombre dans la base factorielle c'est à dire :

15 = 2*3! + 1*2! + 1*1! + 0*0! = (2,1,1,0)
155 = 1*5! + 1*4! + 1*3! + 2*2! + 1*1! + 0*0! (1,1,1,2,1,0)

Pour ton exemple tu fais n=6.
Mettons que tu tire 208 = 5! + 3*4! + 2*3! + 2*2! + 0*1! + 0*0! = (1,3,2,2,0)
Puis tu place les éléments dans ta liste :
au départ tu as liste = [0,1,2,3,4,5] et nouvelle_liste = []
Le premier chiffre est un 1
tu supprime l’élément d'indice 1 de ta liste (ici 1) et tu l'ajoute à nouvelle_liste :
liste = [0,2,3,4,5], nouvelle_liste = [1]
Le deuxième chiffre est un 3
tu supprime l’élément d'indice 3 de ta liste (ici 4) et tu l'ajoute à nouvelle_liste :
liste = [0,2,3,5], nouvelle_liste = [1,4]
...
liste = [], nouvelle_liste = [1,4,3,5,0,2]
Et voilà, c'est très facile à mettre en place et ça sert dans beaucoup de problèmes de dénombrement !

[tbc92]

@Plaxtor
J'aime BEAUCOUP cette idée de décomposition en base factorielle. Ca permet un parallèle direct entre le nombre de permutations n! et un identifiant entre 1 et n! .... Chaque permutation est associée à un nombre de façon unique. Ca a comme un coté pédagogique.

Quand j'ai besoin de trier une liste de façon aléatoire, en fait je fais exactement comme toi, mais sans passer par le calcul de n! :

Je prends un nombre aléatoire entre 1 et n, par exemple i. Je prends l'élément de rang i dans ma liste initiale, et je le mets en tête dans ma liste résultat. Et je le supprime de la liste initiale.
Et je répète l'opération n fois, en prenant à chaque étape E un nombre aléatoire entre 1 et N-E+1.

Ici, j'avais improvisé un algorithme pour trier une liste 'sur elle-même', sans passer par une deuxième liste.
... Mais après réflexion, c'est stupide, l'algorithme qu'on utilise toi ou moi peut parfaitement s'adapter au cas où on utilise une seule liste.

[plaxtor]

En effet, je pense que c'est le moyen le plus intuitif de créer une bijection entre l'ensemble des permutations entre (0,n) et l'ensemble des entiers (0, (n+1)! - 1)
Après comme j'ai dit cela dépend si tu t'autorises à générer un seul nombre aléatoire ou plusieurs. Avec un seul le mieux c'est ainsi, avec plusieurs la méthode que tu décris convient parfaitement (et si on veut faire sur place on permute au lieu de supprimer dans l'un et d'ajouter dans l'autre) !