Ranking and Unranking of Lexicographically Ordered Words: An Average-Case Analysis
| Autor: | Liebehenschel, Jens |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 1997 |
| Předmět: | |
| DOI: | 10.25596/jalc-1997-227 |
| Popis: | We consider all words of length $n$ of a formal language. If these words are arranged according to the lexicographical order, then ranking means to determine the position of a word of the language. Unranking is the inverse operation of ranking. For a given formal language we compute the average length of the shortest prefix of a word to be read to determine its position, if the word is read from left to right. The length of the shortest prefix to be read depends on the language only, not on the ranking algorithm. After having derived a general expression, we demonstrate the result by discussing various concrete applications. Ranking will be analyzed for regular languages, permutations, subsets of sets, the Dyck language, the Motzkin language, extended ordered binary trees according to Zaks, ordered binary trees according to Er, extended ordered $t$-ary trees according to Ruskey, ordered trees with bounded height and Cayley trees. Furthermore, ranking and unranking algorithms will be presented for the languages aforementioned. Journal of Automata, Languages and Combinatorics, Volume 2, Number 4, 1997, 227-268 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|