Constructing k-ary Orientable Sequences with Asymptotically Optimal Length

An orientable sequence of order n over an alphabet \0,1,…, k-1\ is a cyclic sequence such that each length-n substring appears at most once in either direction. When $k= 2$, efficient algorithms are known to construct binary orientable sequences, with asymptotically optimal length, by applying the classic cycle-joining technique. The key to the construction is the definition of a parent rule to construct a cycle-joining tree of asymmetric bracelets. Unfortunately, the parent rule does not generalize to larger alphabets. Furthermore, unlike the binary case, a cycle-joining tree does not immediately lead to a simple successor-rule when k ≥ 3 unless the tree has certain properties. In this paper, we derive a parent rule to derive a cycle-joining tree of k-ary asymmetric bracelets. This leads to a successor rule that constructs asymptotically optimal k-ary orientable sequences in $O(n)$ time per symbol using $O(n)$ space. In the special case when $n=2$, we provide a simple construction of k-ary orientable sequences of maximal length.