Un peu d'info... et des permutations

[Ben314]

(Re) Bonjour.
Un petit problème (dont je n'ai pas la réponse complète...)

Dans un programme informatique, pour fabriquer une permutation de {1..n} au hasard (avec n>=3), on part d'un tableau T[1..n] que l'on initialise avec T[i]=i pour tout i puis on utilise l'un des algo. suivant :

A) Pour i de 1 à n, échanger T[i] avec T[aléatoire entre 1 et n]

B) Pour i de 2 à n, échanger T[i] avec T[aléatoire entre 1 et i]

C) Pour i de 1 à n-1, échanger T[i] avec T[aléatoire entre i et n]

D) Pour i de 1 à n-2, échanger T[i] avec T[aléatoire entre i et n]

- Quel(s) algorithme(s) permettent d'obtenir toutes les permutations de {1..n} ?
- Sont-elles équiprobable (en supposant bien sûr la fonction "aléatoire" réellement... aléatoire) ?
- Plus généralement, pour chacun des algos, peut on donner la proba d'obtenir une permutation donnée d'avance ?

[Doraki]

J'ai bien l'impressoin que A,B,C donnent toutes les permutations ;
et que chaque permutation est équiprobable dans B, C et D.

Quant à la proba d'apparition d'une permutation dans l'algo A.. ça pourrait être plus compliqué

[Ben314]

J'ai bien l'impressoin que A,B,C donnent toutes les permutations ;
et que chaque permutation est équiprobable dans B, C et D.

C'est parfaitement O.K. et les preuves sont trés simple, sauf peut-être la B) qui demande un peu de réflexion (donc... je laisse chercher)

Quant à la proba d'apparition d'une permutation dans l'algo A.. ça pourrait être plus compliqué

C'est effectivement ça que je ne sais pas faire.
La "preuve" que j'ai de la non équiprobabilité dans A) ne donne aucune info concernant la tête des permutations les plus probables. Par exemple Id est elle plus ou moins probable que la moyenne ?
L'autre question (peut-être plus simple) concerne la D) : peut on caractériser trés simplement les permutations générées/non générées ?

[Ben314]

Tient, je vient de réagir que, en ce qui concerne l'algo A), on peut facilement calculer la proba que la permutation tirée soit dans le groupe alterné et, si n>=3, ce n'est pas 1/2...

[Doraki]

Ben lors de chaque étape i, il y a (n-1) chance sur n qu'on ajoute une transposition..
je trouve P(An) = (1 + (-1+2/n)^n) / 2

J'ai pas encore cherché si les permutations données par l'algo D pouvaient être caractérisées simplement.