Las Vegas algorithms to generate universal cycles and de Bruijn sequences uniformly at random
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912763669905408 |
|---|---|
| author | Sawada, Joe Gabrić, Daniel |
| author_facet | Sawada, Joe Gabrić, Daniel |
| contents | We present practical algorithms for generating universal cycles uniformly at random. In particular, we consider universal cycles for shorthand permutations, subsets and multiset permutations, weak orders, and orientable sequences. Additionally, we consider de Bruijn sequences, weight-range de Bruin sequences, and de Bruijn sequences, with forbidden $0^z$ substring. Each algorithm, seeded with a random element from the given set, applies a random walk of an underlying Eulerian de Bruijn graph to obtain a random arborescence (spanning in-tree). Given the random arborescence and the de Bruijn graph, a corresponding random universal cycle can be generated in constant time per symbol. We present experimental results on the average cover time needed to compute a random arborescence for each object using a Las Vegas algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_16545 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Las Vegas algorithms to generate universal cycles and de Bruijn sequences uniformly at random Sawada, Joe Gabrić, Daniel Discrete Mathematics Combinatorics We present practical algorithms for generating universal cycles uniformly at random. In particular, we consider universal cycles for shorthand permutations, subsets and multiset permutations, weak orders, and orientable sequences. Additionally, we consider de Bruijn sequences, weight-range de Bruin sequences, and de Bruijn sequences, with forbidden $0^z$ substring. Each algorithm, seeded with a random element from the given set, applies a random walk of an underlying Eulerian de Bruijn graph to obtain a random arborescence (spanning in-tree). Given the random arborescence and the de Bruijn graph, a corresponding random universal cycle can be generated in constant time per symbol. We present experimental results on the average cover time needed to compute a random arborescence for each object using a Las Vegas algorithm. |
| title | Las Vegas algorithms to generate universal cycles and de Bruijn sequences uniformly at random |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2510.16545 |