{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T08:50:44Z","timestamp":1764838244877,"version":"3.46.0"},"reference-count":26,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T00:00:00Z","timestamp":1764720000000},"content-version":"vor","delay-in-days":336,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2025-03961"],"award-info":[{"award-number":["RGPIN-2025-03961"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2025,10,25]]},"published-print":{"date-parts":[[2025]]},"abstract":"<jats:p>\n                    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\n                    <jats:italic>\n                      <jats:sup>z<\/jats:sup>\n                    <\/jats:italic>\n                    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.\n                  <\/jats:p>","DOI":"10.1051\/ita\/2025019","type":"journal-article","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T08:45:46Z","timestamp":1764837946000},"page":"21","source":"Crossref","is-referenced-by-count":0,"title":["Las Vegas algorithms to generate universal cycles and de Bruijn sequences uniformly at random"],"prefix":"10.1051","volume":"59","author":[{"given":"Joe","family":"Sawada","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Gabri\u0107","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2025,12,3]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1798596.1798598","volume":"6","author":"Ruskey","year":"2010","journal-title":"ACM Trans. Algorithms"},{"key":"R2","unstructured":"Knuth D.E., The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd edn., vol. 2. Addison-Wesley, Reading, MA (1997)."},{"key":"R3","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1006\/jagm.1997.0917","volume":"27","author":"Propp","year":"1998","journal-title":"J. Algorithms"},{"key":"R4","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.tcs.2018.06.039","volume":"743","author":"Gabric","year":"2018","journal-title":"Theoret. Comput. Sci."},{"key":"R5","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1137\/100808782","volume":"26","author":"Ruskey","year":"2012","journal-title":"SIAM J. Discrete Math."},{"key":"R6","first-page":"526","volume":"2","author":"Altschul","year":"1985","journal-title":"Mol. Biol. Evol."},{"key":"R7","unstructured":"Dai Z.-D., Martin K., Robshaw B. and Wild P., Orientable sequences, in Cryptography and Coding III, edited by Ganley M.J.. Oxford University Press (1993) 97-115."},{"key":"R8","first-page":"257","volume":"42","author":"Fleury","year":"1883","journal-title":"J. Math. element."},{"key":"R9","first-page":"130","volume":"14578","author":"Liptak","year":"2024","journal-title":"LATIN 2024. LNCS"},{"key":"R10","unstructured":"Fisher R.A. and Yates F., Statistical Tables for Biological, Agricultural and Medical Research. Oliver and Boyd, London (1938)."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Arndt J., Generating Random Permutations. Phd thesis, Australian National University (2010).","DOI":"10.1007\/978-3-642-14764-7_10"},{"key":"R12","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/S0166-218X(97)81456-4","volume":"71","author":"Kandel","year":"1996","journal-title":"Discrete Appl. Math."},{"key":"R13","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1007\/s00453-022-01047-2","volume":"85","author":"Sawada","year":"2023","journal-title":"Algorithmica"},{"key":"R14","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s00453-011-9544-z","volume":"64","author":"Holroyd","year":"2012","journal-title":"Algorithmica"},{"key":"R15","doi-asserted-by":"crossref","first-page":"20","DOI":"10.37236\/5517","volume":"23","author":"Sawada","year":"2016","journal-title":"Electron. J. Combin."},{"key":"R16","unstructured":"Sawada J., Sears J., Trautrim A. and Williams A., Concatenation trees: a framework for efficient universal cycle and de Bruijn sequence constructions. arXiv preprint arXiv:2308.12405 (2024)."},{"key":"R17","doi-asserted-by":"crossref","first-page":"112022","DOI":"10.1016\/j.disc.2020.112022","volume":"343","author":"Sawada","year":"2020","journal-title":"Discrete Math."},{"key":"R18","unstructured":"OEIS Foundation Inc. Entry A000670 in The On-Line Encyclopedia of Integer Sequences (2025). https:\/\/oeis.org\/{A}000670."},{"key":"R19","unstructured":"De Bruijn sequence and universal cycle constructions (2025). http:\/\/debruijnsequence.org."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Chee Y. M., Etzion T., Nguyen T.L., Ta D.H., Tran V.D. and Vu V.K., Maximum length RLL sequences in de Bruijn graph, arXiv preprint arXiv:2403.01454 (2024).","DOI":"10.2139\/ssrn.5050795"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"D.B. Wilson Generating random spanning trees more quickly than the cover time, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC '96 (Association for Computing Machinery) (1996) 296-303.","DOI":"10.1145\/237814.237880"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Gabri\u0107 D. and Sawada J., Constructing k-ary orientable sequences with asymptotically optimal length. Designs, Codes and Cryptography (2025).","DOI":"10.1007\/s10623-025-01581-4"},{"key":"R23","doi-asserted-by":"crossref","first-page":"1309","DOI":"10.1007\/s12095-024-00742-x","volume":"16","author":"Alhakim","year":"2024","journal-title":"Cryptography and Communications"},{"key":"R24","unstructured":"Burns J. and Mitchell C., Position sensing coding schemes, in Cryptography and Coding III, edited by Ganley M.J.. Oxford University Press (1993) 31-66."},{"key":"R25","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1145\/364520.364540","volume":"7","author":"Durstenfeld","year":"1964","journal-title":"Commun. ACM"},{"key":"R26","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1109\/TIT.2019.2928292","volume":"66","author":"Gabric","year":"2020","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2025019\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T08:45:50Z","timestamp":1764837950000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2025019"}},"subtitle":[],"editor":[{"given":"Vincent","family":"Vajnovszki","sequence":"first","affiliation":[]},{"given":"Antonio","family":"Bernini","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":26,"alternative-id":["ita250017"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2025019","relation":{},"ISSN":["0988-3754","2804-7346"],"issn-type":[{"type":"print","value":"0988-3754"},{"type":"electronic","value":"2804-7346"}],"subject":[],"published":{"date-parts":[[2025]]}}}