Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Counting and generating permutations using timed languages (long version)

Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00820373
Contributor : Nicolas Basset <>
Submitted on : Saturday, May 4, 2013 - 11:35:09 AM
Last modification on : Thursday, March 26, 2020 - 9:17:45 PM
Long-term archiving on: : Monday, August 5, 2013 - 3:05:08 AM

File

combi13.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00820373, version 1

Collections

Citation

Nicolas Basset. Counting and generating permutations using timed languages (long version). 2013. ⟨hal-00820373v1⟩

Share

Metrics

Record views

100

Files downloads

27