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 \(2^{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 \(O(n)\) time per bit and only \(O(n)\) space. Following a similar approach, we also present an efficient algorithm to construct the Prefer-opposite de Bruijn sequence.

An orientable sequence of order n is a cyclic binary sequence such that each length-n substring appears at most once in either direction. Maximal length orientable sequences are known only for n ≤ 7, and a trivial upper bound on their length is 2^{n-1} - 2^{⌊(n-1)/2⌋}. This paper presents the first efficient algorithm to construct orientable sequences with asymptotically optimal length; more specifically, our algorithm constructs orientable sequences via cycle-joining and a successor-rule approach requiring O(n) time per bit and O(n) space. This answers a longstanding open question from Dai, Martin, Robshaw, Wild [Cryptography and Coding III (1993)]. Our sequences are applied to find new longest-known orientable sequences for n ≤ 20.

Knuth assigned the following open problem a difficulty rating of 48/50 in The Art of Computer Programming Volume 4A : For odd n ≥ 3, can the permutations of { 1,2,… , n } be ordered in a cyclic list so that each permutation is transformed into the next by applying either the operation σ, a rotation to the left, or τ, a transposition of the first two symbols? The Sigma-Tau problem is equivalent to finding a Hamilton cycle in the directed Cayley graph generated by σ = (1 2 ⋅ n ) and τ = (1 2). In this article, we solve the Sigma-Tau problem by providing a simple O ( n )-time successor rule to generate successive permutations of a Hamilton cycle in the aforementioned Cayley graph.

We present a simple framework for constructing$k$-ary de Bruijn sequences, and more generally, universal cycles, via successor rules. The framework is based on the often used method of joining disjoint cycles. It generalizes several previously known de Bruijn sequence constructions based on the pure cycling register and is applied to derive a new construction that is perhaps the simplest of all successors. Furthermore, it generalizes an algorithm to construct binary de Bruijn sequences based on any arbitrary nonsingular feedback function. The framework is applied to derive and prove the correctness of successors to efficiently construct 1) universal cycles for$k$-ary strings of length$n$whose weight is bounded by some$w$and 2) universal cycles for permutations. It has also been subsequently applied to find the first universal cycle constructions for weak orders.

Nijenhuis and Wilf asked the following question in their Combinatorial Algorithms textbook from 1975: Can the permutations of {1, 2, …, n} be ordered so that each permutation is transformed into the next by applying either the operation σ, a rotation to the left, or τ, a transposition of the first two symbols? Knuth rated the challenge of finding a cyclic solution for odd n (cycles do not exist for even n > 2) at 48/50 in The Art of Computer Programming, which makes it Volume 4's hardest open problem since the ‘middle levels’ problem was solved by Mütze. In this paper we solve the 40 year-old question by Nijenhuis and Wilf, by providing a simple successor rule to generate each successive permutation. We also present insights into how our solution can be modified to find a Hamilton cycle for odd n.

De Bruijn sequences are circular strings of length $2^n$ whose length n substrings are the binary strings of length n. Our focus is on creating circular strings of length $\binom{n}{w}$ for the binary strings of length n with weight (number of 1s) equal to w. In this case, each fixed-weight string can be encoded by its first $n{-}1$ bits since the final bit is redundant. For this reason, we construct circular strings of length $\binom{n-1}{w}+\binom{n-1}{w-1}$ whose length $n{-}1$ substrings are the binary strings of length $n{-}1$ with weight w or $w{-}1$. Our construction is reminiscent of the construction for the lexicographically least de Bruijn sequence, except the underlying algorithm is applied to cool-lex order instead of lexicographic order. The construction can be efficiently implemented so that successive blocks of n bits are generated in constant amortized time while using $O(n \log n)$-space. This article's results were also used to create de Bruijn sequences for binary strings of length n with a specified maximum weight.

An open meandric system is a planar configuration of acyclic curves crossing an infinite horizontal line in the plane such that the curves may extend in both horizontal directions. We present a fast, recursive algorithm to exhaustively generate open meandric systems with n crossings. We then illustrate how to modify the algorithm to generate unidirectional open meandric systems (the curves extend only to the right) and nonisomorphic open meandric systems where equivalence is taken under horizontal reflection. Each algorithm can be modified to generate systems with exactly k curves. In the unidirectional case when k = 1, we can apply a minor modification along with some additional optimization steps to yield the first fast and simple algorithm to generate open meanders.

A signed binary representation (SBR) of an integer N is a string $a_b\cdots a_2a_1a_0$ over the alphabet $\{-1,0,1\}$ such that $N = \sum_{i=0}^b a_i2^i$. An SBR of an integer N is said to be minimal if the number of nonzero digits is minimum. In this paper, we describe a simple 3–close Gray code for listing all minimal SBRs of an integer N. The algorithm is implemented to run in constant amortized time. In addition, we identify the values for N that have the maximum number of minimal SBRs given the length of the binary representation of N.

This article has two main results. First, we develop a simple algorithm to list all nonisomorphic rooted plane trees in lexicographic order using a level sequence representation. Then, by selecting a unique centroid to act as the root of a free plane tree, we apply the rooted plane tree algorithm to develop an algorithm to list all nonisomorphic free plane trees. The latter algorithm also uses a level sequence representation and lists all free plane trees with a unique centroid first followed by all free plane trees with two centroids. Both algorithms are proved to run in constant amortized time using straightforward bounding methods.

Using a new string representation, we develop two algorithms for generating nonisomorphic chord diagrams. Experimental evidence indicates that the latter of the two algorithms runs in constant amortized time. In addition, we use simple counting techniques to derive a formula for the number of nonisomorphic chord diagrams.

A bracelet is the lexicographically smallest element in an equivalence class of strings under string rotation and reversal. We present a fast, simple, recursive algorithm for generating (i.e., listing) k-ary bracelets. Using simple bounding techniques, we prove that the algorithm is optimal in the sense that the running time is proportional to the number of bracelets produced. This is an improvement by a factor of n (where n is the length of the bracelets being generated) over the fastest, previously known algorithm to generate bracelets. (A correction has been added to the end of this article.)

The trace of a degree n polynomial f(x) over GF(q) is the coefficient of x n-1 . Carlitz [Proc. Amer. Math. Soc., 3 (1952), pp. 693--700] obtained an expression I q (n,t) for the number of monic irreducible polynomials over GF(q) of degree n and trace t. Using a different approach, we derive a simple explicit expression for I q (n,t). If t>0, I q (n,t) = (\sum \mu(d) q^{n/d})/(qn)$, where the sum is over all divisors d of n which are relatively prime to q. This same approach is used to count L q (n,t), the number of q-ary Lyndon words whose characters sum to t mod q. This number is given by L q (n,t) = (\sum {\rm gcd}(d,q) \mu(d) q^{n/d})/(qn)$, where the sum is over all divisors d of n for which gcd(d,q)|t. Both results rely on a new form of Möbius inversion.

A k-ary necklace is an equivalence class of k-ary strings under rotation. A necklace of fixed density is a necklace where the number of zeros is fixed. We present a fast, simple, recursive algorithm for generating (i.e., listing) fixed-density k-ary necklaces or aperiodic necklaces. The algorithm is optimal in the sense that it runs in time proportional to the number of necklaces produced.