Résumé : Tirer une permutation aléatoire uniforme de taille n n'est pas bien difficile, et on sait assez bien à quoi c'est censé ressembler. Qu'en est-il si on souhaite imposer des restrictions sur le type cyclique? Il n'est pas bien difficile non plus de tirer une permutation aléatoire ayant un nombre prédéterminé de points fixes - il suffit de savoir tirer un dérangement, et à grande taille, près de 37% des permutations sont des dérangements. On a donc facilement un algorithme qui va nécessiter en moyenne O(n) tirages d'entiers aléatoires d'ordre O(n). Dans ce travail en commun avec Romaric Duvignau (EJC, 2016), nous montrons comment cela peut être fait avec n+O(1) tirages en moyenne, par un rejet anticipé. Cela est possible grâce à la construction d'un arbre de génération pour les permutations, qui a la particularité de "fixer" très rapidement, et aussi vite qu'il est possible, le nombre de points fixes. Comme conséquences faciles, on a alors des algorithmes tout aussi efficaces pour tirer des permutations aléatoires avec un nombre prescrit de points fixes. Le passage de "points fixes" à "cycles d'une longueur k donnée" est possible, mais sensiblement moins élégant.

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr