Decoding universal cycles for t-subsets and t-multisets by decoding bounded-weight de Bruijn sequences
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915857426284544 |
|---|---|
| author | Gabric, Daniel Imam, Wazed Jones, Lukas Janik Sawada, Joe |
| author_facet | Gabric, Daniel Imam, Wazed Jones, Lukas Janik Sawada, Joe |
| contents | A universal cycle for a set S of combinatorial objects is a cyclic sequence of length |S| that contains a representative of each element in S exactly once as a substring. Despite the many universal cycle constructions known in the literature for various sets including k-ary strings of length n, permutations of order n, t-subsets of an n-set, and t-multisets of an n-set, remarkably few have efficient decoding (ranking/unranking) algorithms. In this paper we develop the first polynomial time/space decoding algorithms for bounded-weight de Bruijn sequences for strings of length nover an alphabet of size k. The results are then applied to decode universal cycles for t-subsets and t-multisets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_11934 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Decoding universal cycles for t-subsets and t-multisets by decoding bounded-weight de Bruijn sequences Gabric, Daniel Imam, Wazed Jones, Lukas Janik Sawada, Joe Discrete Mathematics Information Theory Combinatorics A universal cycle for a set S of combinatorial objects is a cyclic sequence of length |S| that contains a representative of each element in S exactly once as a substring. Despite the many universal cycle constructions known in the literature for various sets including k-ary strings of length n, permutations of order n, t-subsets of an n-set, and t-multisets of an n-set, remarkably few have efficient decoding (ranking/unranking) algorithms. In this paper we develop the first polynomial time/space decoding algorithms for bounded-weight de Bruijn sequences for strings of length nover an alphabet of size k. The results are then applied to decode universal cycles for t-subsets and t-multisets. |
| title | Decoding universal cycles for t-subsets and t-multisets by decoding bounded-weight de Bruijn sequences |
| topic | Discrete Mathematics Information Theory Combinatorics |
| url | https://arxiv.org/abs/2603.11934 |