{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T20:49:03Z","timestamp":1772052543428,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"University Research Board of the American University of Beirut","award":["27190"],"award-info":[{"award-number":["27190"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"<jats:p>\n            The greedy Prefer-same de Bruijn sequence construction was first presented by Eldert, Gray, Gurk, and Rubinoff in 1958. As a greedy algorithm, it has one major downside: it requires an exponential amount of space to store the length\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(2^{n}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            de Bruijn sequence. Though de Bruijn sequences have been heavily studied over the last 60 years, finding an efficient construction for the Prefer-same de Bruijn sequence has remained a tantalizing open problem. In this article, we unveil the underlying structure of the Prefer-same de Bruijn sequence and solve the open problem by presenting an efficient algorithm to construct it using\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            time per bit and only\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            space. Following a similar approach, we also present an efficient algorithm to construct the Prefer-opposite de Bruijn sequence.\n          <\/jats:p>","DOI":"10.1145\/3679015","type":"journal-article","created":{"date-parts":[[2024,7,26]],"date-time":"2024-07-26T16:01:12Z","timestamp":1722009672000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Constructions of the Prefer-Same and Prefer-Opposite de Bruijn Sequences"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-2886-6226","authenticated-orcid":false,"given":"Evan","family":"Sala","sequence":"first","affiliation":[{"name":"University of Guelph, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7364-2993","authenticated-orcid":false,"given":"Joe","family":"Sawada","sequence":"additional","affiliation":[{"name":"University of Guelph, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2995-3740","authenticated-orcid":false,"given":"Abbas","family":"Alhakim","sequence":"additional","affiliation":[{"name":"American University of Beirut, Beirut, Lebanon"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,4]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.4169\/000298910x515794"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.11.024"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.11.018"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30004-7"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90149-0"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.2023"},{"key":"e_1_3_4_8_2","first-page":"461","article-title":"A combinatorial problem","volume":"8","author":"Bruijn N. G. de","year":"1946","unstructured":"N. G. de Bruijn. 1946. A combinatorial problem. Indagationes Mathematicae 8 (1946), 461\u2013467.","journal-title":"Indagationes Mathematicae"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2018.03.006"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90017-2"},{"key":"e_1_3_4_11_2","first-page":"70","article-title":"Shifting counters","volume":"77","author":"Eldert C.","year":"1958","unstructured":"C. Eldert, H. Gray, H. Gurk, and M. Rubinoff. 1958. Shifting counters. AIEE Transactions 77 (1958), 70\u201374.","journal-title":"AIEE Transactions"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(87)90035-5"},{"key":"e_1_3_4_13_2","first-page":"257","article-title":"Deux problemes de geometrie de situation","volume":"42","author":"Fleury M.","year":"1883","unstructured":"M. Fleury. 1883. Deux problemes de geometrie de situation. Journal de mathematiques elementaires 42 (1883), 257\u2013261.","journal-title":"Journal de mathematiques elementaires"},{"key":"e_1_3_4_14_2","first-page":"107","article-title":"Solution to question nr. 48","volume":"1","author":"Flye Sainte-Marie C.","year":"1894","unstructured":"C. Flye Sainte-Marie. 1894. Solution to question nr. 48. L\u2019interm\u00e9diaire des Math\u00e9maticiens 1 (1894), 107\u2013110.","journal-title":"L\u2019interm\u00e9diaire des Math\u00e9maticiens"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90091-X"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1024041"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(77)90059-0"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90002-X"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.06.039"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112780"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2018.07.010"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2928292"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/578271"},{"key":"e_1_3_4_24_2","first-page":"257","article-title":"Deux problemes de geometrie de situation","volume":"42","author":"Hierholzer C.","year":"1873","unstructured":"C. Hierholzer. 1873. Deux problemes de geometrie de situation. Journal de mathematiques elementaires 42 (1873), 257\u2013261.","journal-title":"Journal de mathematiques elementaires"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90028-D"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-022-01108-1"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5079-4"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1934-05988-3"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.171285098"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-016-0322-4"},{"key":"e_1_3_4_31_2","unstructured":"E. Sala. 2018. Exploring the greedy constructions of de Bruijn sequences. Master\u2019s thesis University of Guelph."},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2015.08.002"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40104-6_46"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90072-2"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3679015","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3679015","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:15Z","timestamp":1750294695000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3679015"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3679015"],"URL":"https:\/\/doi.org\/10.1145\/3679015","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,4]]},"assertion":[{"value":"2020-09-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-05","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}