Decoding universal cycles for t t -subsets and t t -multisets by decoding bounded-weight de Bruijn sequences

Daniel Gabrić, Wazed Imam, Lukas Janik-Jones, Joe Sawada · 2026

Read Decoding universal cycles for t t -subsets and t t -multisets by decoding bounded-weight de Bruijn sequences by Daniel Gabrić, Wazed Imam, Lukas Janik-Jones, Joe Sawada (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-11934.txt.

Introduction

Gabric and co-authors give the first fast decoding method for bounded-weight de Bruijn sequences. A universal cycle packs every object of a set into one cyclic string, each appearing once as a substring. Many cycle constructions exist, yet few come with efficient ranking and unranking. Their polynomial-time and space decoder handles strings of length n over a k-letter alphabet with bounded weight. The same machinery then decodes universal cycles for t-subsets and t-multisets.

Catalog record

CREATORDaniel Gabrić, Wazed Imam, Lukas Janik-Jones, Joe Sawada
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47694
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.11934

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Decoding universal cycles for t t -subsets and t t -multisets by decoding bounded-weight de Bruijn sequences Daniel Gabrić, Wazed Imam, Lukas Janik-Jones, Joe Sawada Abstract A universal cycle for a set 𝐒 \mathbf{S} of combinatorial objects is a cyclic sequence of length | 𝐒 | |\mathbf{S}| that contains a representative of each element in 𝐒 \mathbf{S} exactly once as a substring. Despite the many universal cycle constructions known in the literature for various sets including k k -ary strings of length n n , permutations of order n n , t t -subsets of an n n -set, and t t -multisets of an n 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 n n over an alphabet of size k k . The results are then applied to decode universal cycles for t t -subsets and t t -multisets. University of Guelph, Canada University of Guelph, Canada University of Guelph, Canada University of Guelph, Canada † † runningtitle: Decoding universal cycles † † runningauthor: † † copyright: 1 Introduction A universal cycle for a set \mathbf{S} of combinatorial objects is a cyclic sequence of length |\mathbf{S}| that contains a representation of each element in \mathbf{S} exactly once as a substring. Unless otherwise stated, assume that the representative of each element \mathbf{s}\in\mathbf{S} is simply \mathbf{s} itself. In cases where \mathbf{s} is not a string, then its representative will be clearly articulated. The following “fundamental questions” can be asked of any set \mathbf{S} [ 6 ] : (i) Do universal cycles exist for \mathbf{S} ? (ii) How many universal cycles for \mathbf{S} are there? (iii) Can a universal cycle for \mathbf{S} be (efficiently) constructed? (iv) Does a universal cycle for \mathbf{S} exist with properties that make it efficiently decodable ? In other words, are there efficient ranking and ranking algorithms for a specific universal cycle of \mathbf{S} ? There are numerous results pertaining to the first three questions for a wide variety of interesting sets \mathbf{S} ; see for instance [ 12 , 6 , 18 , 1 , 9 , 7 ] . The decoding question, though, has proven to be more elusive. Let \mathbf{S}_{k}(n) denote the set of all length- n strings over \{\mathtt{1,2,\ldots,k}\} . A universal cycle for \mathbf{S}_{k}(n) is known as a de Bruijn sequence . The weight of a string is the sum of its symbols. Let \mathbf{S}_{k}(n,w^{\uparrow}) denote the subset of \mathbf{S}_{k}(n) containing the strings with weight at least w . Let \mathbf{S}_{k}(n,w_{\downarrow}) denote the subset of \mathbf{S}_{k}(n) containing the strings with weight at most w . Universal cycles for \mathbf{S}_{k}(n,w^{\uparrow}) and \mathbf{S}_{k}(n,w_{\downarrow}) are known as a bounded-weight de Bruijn sequences . In this paper we present efficient ranking and unranking algorithms for a bounded-weight de Bruin sequence. The algorithms are applied to efficiently decode universal cycles for t -subsets and t -multisets. They are the first known efficient algorithms to decode specific universal cycles for these objects. Decoding universal cycles. Let \mathcal{U}=u_{1}u_{2}\cdots u_{m} be a universal cycle for a set \mathbf{S} of length- n strings. The rank of a string \mathbf{s}\in\mathbf{S} is the starting index where \mathbf{s} is found in \mathcal{U} . If \mathbf{s} is a prefix of \mathcal{U} then it has rank 1; if \mathbf{s} starts at the last symbol of \mathcal{U} and wraps around, then it has rank |\mathbf{S}| . Given a rank r , the unranking process determines the string \mathbf{s}\in\mathbf{S} starting at index r in \mathcal{U} . Together, ranking and unranking algorithms allow for a universal cycle to be decoded . Any universal cycle can be decoded by traversing the sequence until a given string, or rank, is discovered; however, this requires O(|{\bf S}|) time. Similarly, a look-up table can be applied to store the position of a given string, but this requires \Theta(|{\bf S}|) space. We say a decoding algorithm is efficient if the ranking and unranking algorithms run in polynomial time and require polynomial space, with respect to the size of the alphabet and the length of each string \mathbf{s} . The efficient decoding of a universal cycle is necessary when it is applied to robotic position sensing (vision) applications [ 3 , 8 ] . There are numerous de Bruijn sequence constructions that apply a variety of different algorithmic approaches; see, for instance [ 12 , 9 , 7 ] . However, somewhat surprisingly, only the lexicographically smallest de Bruijn sequence for \mathbf{S}_{k}(n) is known to be efficiently decodable for all n and k [ 21 , 31 ] . We review the decoding approach for this de Bruijn sequence in Section 3 . A recursively constructed de Bruijn sequence can be efficiently decoded in the binary case, but not for all n and k [ 23 , 32 ] . See also [ 20 , p.317, ex.97-99] . The only other known efficient decoding algorithms are for universal cycles of permutations using a shorthand representation [ 26 , 15 ] . This highlights the difficulty in discovering such decoding algorithms. t -subsets and t -multisets. Let \mathbf{Subset}(n,t) denote the set of all t -subsets of \{\mathtt{1,2,\ldots,n}\} . Universal cycles for \mathbf{Subset}(n,t) have been considered using a standard string representation for each subset, where, for instance, either \mathtt{12} or \mathtt{21} can be used to represent the subset \{1,2\} [ 6 , 19 , 17 , 18 , 24 ] . Using this representation, universal cycles for t -subsets exist only if n divides {n\choose t} . A t -subset can also be represented by a length- n binary string with t ones. A shorthand representation excludes the final redundant bit. Applying this shorthand representation, universal cycles for t -subsets can be efficiently constructed for all 1\leq t\leq n [ 25 ] . No efficient decoding algorithms are known for these universal cycles. In [ 5 ] , a labelled graph is applied to represent a t -subset. With this representation they demonstrate the existence of a universal cycle for t -subsets, however, no efficient construction is provided. A difference representation was recently described in [ 4 ] . Given a subset \{\mathtt{s}_{1},\mathtt{s}_{2},\ldots,\mathtt{s}_{t}\} with elements listed in increasing order, its difference representative is the length- t string where the first symbol is \mathtt{s}_{1} and the j -th symbol is \mathtt{s}_{j}-\mathtt{s}_{j-1} for 1<j\leq t . For example, the difference representatives for \mathbf{Subset}(5,3) = \{\mathtt{\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\},\{2,3,4\},\{2,3,5\},\{2,4,5\},\{3,4,5\}}\} are given by \mathtt{111,112,113,121,122,131,211,212,221}, and \mathtt{311} , respectively. In general, the difference representatives for \mathbf{Subset}(n,t) correspond to the strings in \mathbf{S}_{n-t+1}(t,n_{\downarrow}) . Let \mathbf{Multiset}(n,t) denote the set of all t -multisets of \{\mathtt{0,1,\ldots,n-1}\} . Universal cycles for \mathbf{Multiset}(n,t) have been considered using a standard string representation for each subset, where, for instance, either \mathtt{112} , \mathtt{121} , or \mathtt{211} can be used to represent the multiset \{1,1,2\} [ 19 , 16 ] . Using this representation, universal cycles for t -multisets exist only if n divides {n+t-1\choose t} . Like with t -subsets, we can also apply a difference representation for t -multisets [ 4 ] . Given a multiset \{\mathtt{m}_{1},\mathtt{m}_{2},\ldots,\mathtt{m}_{t}\} with elements listed in non-decreasing order, its difference representative is the length t string where the first symbol is \mathtt{m}_{1} and the

Read the complete text