Counting and generating permutations using timed languages (long version)
Résumé
The signature of a permutation $\sigma$ is a word $p(\sigma)\subseteq\{U,D\}^*$ whose $i^{th}$ letter is $U$ when $\sigma$ goes ''up'' (i.e. $\sigma(i)>\sigma(i+1)$) and is $D$ when $\sigma$ goes ''down'' (i.e. $\sigma(i)<\sigma(i+1)$). Combinatorics of permutations with a prescribed signature is a quite well explored topics. Languages of signatures permit to express a broad number of classes of permutations (e.g. the permutations without two consecutive downs). Here we state and address the two problems of counting and randomly generating in the set $p^{-1}(L)$ of permutations whose signature is in a given regular language $L\subseteq \{U,D\}^*$. First we give an algorithm that computes a closed form formula for the exponential generating function of $p^{-1}(L)$. Then we give an algorithm that generates randomly the $n$-length permutations of $p^{-1}(L)$ in a uniform manner i.e. all the permutations of a given length with a signature in $L$ are equally probable to be returned. Both contributions are based on a geometric interpretation of a subclass of timed regular languages.
Origine : Fichiers produits par l'(les) auteur(s)