## How to compute de Bruijn sequences for non-power-of-two-sized alphabets?

I'm trying to compute de Bruijn sequences for alphabets which have a number of characters which is *not* a power of two.

For alphabets with a 2^k characters, calculating de Bruijn sequences is easy: There are several simple rules, such as "Prefer Ones" and "Prefer Opposites" which work for generating B(2,n). B(2^k,n) is exactly the same as B(2,kn), if you read the 1s and 0s as binary codes for the actual characters in your alphabet. E.g., you can interpret B(2,8n) as being over n-length sequences of bytes.

Prefer Ones is quite simple: Write n zeros. Then, always write a one unless it would cause the repetition of an n-length string; otherwise, write a zero.

Presently, I don't see how to generalize such rules to non-power-of-two-sized alphabets.

There's a general method for calculating de Bruijn sequences via graphs: Let each n-length sequence generated by your alphabet be a node; put an edge from A to B iff the rightmost n-1 characters of A are the same as the leftmost n-1 characters of B. Label each edge with the last character of the string in the head vertex. Any Eulerian path through this graph will generate a de Bruijn sequence, and the peculiar construction we used guarantees that there will be at least one such path. We can use Fleury's Algorithm to (nondeterministically) construct an Eulerian path:

- Choose a vertex.
- Leave that vertex via some edge and delete that edge, only choosing edges whose deletion would disconnect the vertex from the graph if there is no alternative.
- Append to your string the label of the edge you just deleted.
- Goto 2 until all edges are gone.

The resulting string will be a de Bruijn sequence.

This algorithm is somewhat more complex to implement than Prefer Ones. The simplicity of Prefer Ones is that one needs only to consult the output already generated to determine what to do. Is there a straightforward way to generalize Prefer Ones (or, possibly Prefer Opposites) to alphabets of non-power-of-two sizes?

This is my C++ implementation of the algorithm in Figure 1 from a paper by Sawada and Ruskey:

void debruijn(unsigned int t, unsigned int p, const unsigned int k, const unsigned int n, unsigned int* a, boost::function<void (unsigned int*,unsigned int*)> callback) { if (t > n) { // we want only necklaces, not pre-necklaces or Lyndon words if (n % p == 0) { callback(a+1, a+p+1); } } else { a[t] = a[t-p]; debruijn(t+1, p, k, n, a, callback); for (unsigned int j = a[t-p]+1; j < k; ++j) { a[t] = j; debruijn(t+1, t, k, n, a, callback); } } } struct seq_printer { const std::vector<char>& _alpha; seq_printer(const std::vector<char>& alpha) : _alpha(alpha) {} void operator() (unsigned int* a, unsigned int* a_end) const { for (unsigned int* i = a; i < a_end; ++i) { std::cout << _alpha[*i]; } } }; ... std::vector<char> alpha; alpha.push_back('a'); alpha.push_back('b'); alpha.push_back('c'); unsigned int* a = new unsigned int[N+1]; a[0] = 0; debruijn(1, 1, alpha.size(), N, a, seq_printer(alpha)); if (N > 1) std::cout << alpha[0]; std::cout << std::endl; delete[] a;

The full reference for the paper is: Joe Sawada and Frank Ruskey, "An Efficient Algorithm for Generating Necklaces with Fixed Density", SIAM Journal of Computing *29*:671-684, 1999.

**De Bruijn sequence,** I'm trying to compute de Bruijn sequences for alphabets which have a number of characters which is not a power of two.For alphabets with a� The 'prefer-1' algorithm works by having a current word, shifting out the first bit and then appending a new bit. Such a current word - which essentially represents the tail of the sequence constructed thus far - could be housed in a machine word (word-sized variable or register) for lengths up to 32 or 64 bits. The new bit that you decide on during each iteration can then be converte

According to this web page at the combinatorial group of the CS department at UVic, there's a result due to Fredericksen that you can generate a de Bruijn sequence (in fact, the lexicographically smallest one) by concatenating "the lexicographic sequence of Lyndon words of lengths divisible by n". There's even source code to build the sequence that you can request.

**De Bruijn Sequence,** In combinatorial mathematics, a de Bruijn sequence of order n on a size-k alphabet A is a cyclic Goal: to construct a B(2, 4) de Bruijn sequence of length 24 = 16 using on a PIN-like code lock that does not have an "enter" key and accepts the last n A de Bruijn sequence can be used to quickly find the index of the least� I was reading about De Bruijn sequences, and in wikipedia it was written that: The number of distinct De Brujin sequences B(k,n),Where k is the size of the alphabet and n is the length of each wor

Are you only interested in a generalization of Prefer Ones or do you just want a not so complex algorithm? If the latter is true then maybe Frank Ruskey's recursive implementation could be of help.

A year ago I translated that one to Ruby.

# De Bruijn sequence # Original implementation by Frank Ruskey (1994) # translated to C by Joe Sawada # and further translated to Ruby by Jonas Elfström (2009) @n=4 @k=10 @a=[0] @sequence=[] def debruijn(t, p, alike) if t>@n if @n%p==0 1.upto(p) {|j| @sequence<<@a[j]} end else @a[t]=@a[t-p] if @a[t]>0 debruijn(t+1,p,alike+1) else debruijn(t+1,p,alike) end (@a[t-p]+1).upto(@k-1) {|j| @a[t]=j debruijn(t+1,t,alike+1) } end end debruijn(1,1,0) print @sequence.join

Uckelman noticed that the `alike`

variable does nothing. The following produces the same sequence.

@n=4 @k=10 @a=[0] @sequence=[] def debruijn(t, p) if t>@n if @n%p==0 1.upto(p) {|j| @sequence<<@a[j]} end else @a[t]=@a[t-p] debruijn(t+1,p) (@a[t-p]+1).upto(@k-1) {|j| @a[t]=j debruijn(t+1,t) } end end debruijn(1,1) print @sequence.join

**[PDF] Multi de Bruijn Sequences,** Binary alphabet. According to De Bruijn himself , the existence of De Bruijn sequences were first proved, for the case of alphabets with two elements, by Camille� de Bruijn sequence, k=2, n=3 The following is a de Bruijn sequence of a k=2 sized alphabet with string length of n=3 . Please note that the sequence is circular, i.e. it wraps "around the end", indicated by setting the first n-1 digits last in the sequence (inside parenthesis).

or you can use:

def de_bruijn(k, n): a = [0] * k * n sequence = [] def db(t, p): if t > n: if n % p == 0: for j in range(1, p + 1): sequence.append(a[j]) else: a[t] = a[t - p] db(t + 1, p) for j in range(a[t - p] + 1, k): a[t] = j db(t + 1, t) db(1, 1) return sequence print de_bruijn(2,9)

**De Bruijn sequence,** cyclic de Bruijn sequence is a cyclic sequence over alphabet Ω (of size q) in which 2. GLENN TESLER. Reference. Multiplicity Alphabet size Word size. [7] de For m, q, k ≥ 1, we will compute the number of linearized cyclic (Sec. 2) A sequence s is primitive if its length is positive and s is not a power. 1. Multi de Bruijn sequences of various types De nition Notation Alphabet Alphabet size q= j j Word size k Multiplicity of each k-mer m Rotational order of a sequence d; must divide into m Speci c k-mer that sequences start with y Number of multi de Bruijn sequences of each type. In these functions that give set sizes,

Duval's algorithm does the same thing iteratively (In Python this time):

def debruijn(k, n): v = [0 for _ in range(n)] l = 1 r = [] while True: if n % l == 0: r.extend(v[0:l]) for i in range(l, n): v[i] = v[i-l] l = n while l > 0 and v[l-1] >= k-1: l-=1 if l == 0: break v[l-1] += 1 return r print(debruijn(3,5))

**[PDF] De Bruijn Sequences Revisited,** In combinatorial mathematics, a k-ary De Bruijn sequence B(k, n) of order n, for general alphabet size in place of 2, with an algorithm for constructing them. that does not have an "enter" key and accepts the last n digits entered. A De Bruijn sequence can be used to quickly find the index of the LSB or� algorithm - How to compute de Bruijn sequences for non-power-of-two-sized alphabets? I'm trying to compute de Bruijn sequences for alphabets which have a number of characters which is not a power of two. For alphabets with a 2^k characters, calculating de Bruijn sequences is easy: The…

**(PDF) Stretching de Bruijn sequences,** A (non-circular) de Bruijn sequence w of order n is a word such that every word of and is (am!)an−m for 1 ≤ m ≤ n, where a is the size of the alphabet. For example, 00110 is a binary de Bruijn sequence of order 2 since each binary words over the binary alphabet; the former also calculated the formula 22n for the . The de Bruijn graph G(S;k) for a string S and a natural number k is a graph constructed as follows: For each distinct k-mer of S the de Bruijn graph contains a node representing this k-mer. If u= S[i::i+ k] and v= S[i+ 1::i+ 1 + k] u and v are connected by an edge u!v. Two nodes u and v can be merged into

**(PDF) A recursive construction of nonbinary de Bruijn sequences,** Find, read and cite all the research you need on ResearchGate. two cycles into one de Bruijn sequence in B(n+k, q). While the cycles of a de Bruijn cycle, where qis any alphabet size (that need not be a power of prime). A de Bruijn sequence is identiﬁed with a de Bruijn cycle in an obvious w ay. F or example, the cycle (00 , 01 , 11 , 10 , 00) of B (2 , 2) is identiﬁed with 00110. It is customary , see Lemp

**Perfect factors in the de Bruijn graph,** PDF | This paper presents a method to find new de Bruijn sequences based on generalize to non-binary alphabets and consider de Bruijn digraphs of non- the two alternating strings of size n010 . . . and its complement zn+ 1 which can Bruijn cycle in Bnto a higher order Bn+k, for some integer kthat is a power of 2, by . A single-shot colored structured light method based on a Debruijn sequence is implemented. This particular algorithm is based on the research by Zhang et al in 2002 [1]. The paper is available at [2]. [1] - Li Zhang, Brian Curless, and Steven M. Seitz - Rapid Shape Acquisition Using Color Structured Light and Multi-pass Dynamic Programming

##### Comments

- +1; another place to look for code and a detailed description is the FXT library and "fxtbook" (see sections 18.1 and 18.2).
- I'm interested in whether Prefer Ones is extensible somehow, but also other simple algorithms. Thanks. I now have a reason to learn the syntax for Ruby. Heh.
- Is the paper from which you got the algorithm this one?
- Also, what's the reason for the
`alike`

parameter? It appears to do nothing. - I remember finding the C source code on a page somewhere and not in a PDF document. Unfortunately I don't remember where and I can't seem to find it now.
- Further note: This doesn't quite generate de Bruijn sequences. Rather, for n > 1, it generates everything except the last character. (I know that you can define them as circular strings, so leaving off the last letter is ok in that setting. It's just surprising here, if you were expecting to have the join point represented at both ends.)
- Your program's missing some words. Every word's missing for the tuple (k, n) = (0, n); every word 'kk…00' (with
`k`

= "your input variable k for`de_bruijn`

; consisting only of a block of the last letter of the alphabet followed by a block of the first letter) I'm writing something in order to improve this… but I don't know how to fix your code without workaround (yet).