Chapter 5 · Euler Tours and Hamilton Cycles
De Bruijn Sequences
The shortest string containing every k-mer: an Eulerian cycle on (k−1)-bit states.
A de Bruijn sequence B(k, n) is a cyclic string over an alphabet of size k in which every length-n word appears exactly once as a (cyclic) substring. Its length is kn, and it is optimal: kn distinct windows need at least kn positions.
Vertices = the kn-1 words of length n-1. For each vertex w = a1 … an-1 and each letter b, add an edge w → a2 … an-1 b labelled b. Every vertex then has out-degree k and in-degree k, and the graph is strongly connected (shift away any window). So it is Eulerian (Euler Tours: When They Exist), and an Eulerian circuit uses each edge once — each edge is exactly one length-n word (its label plus the tail of the source). Reading edge labels along the tour gives B(k,n).
int k, n, N; // N = k^(n-1)
vector<int> a(k * n), result;
vector<int> ptr; // per-vertex next letter to try
void dbg(int v) { // Hierholzer on implicit graph
for (int& c = ptr[v]; c < k; c++) {
int nxt = (v * k + c) % N;
dbg(nxt);
result.push_back(c); // append on the way BACK
}
}
// result reversed (as built by the recursion) = the sequence, length k^ndbg is Hierholzer's post-order emission (Hierholzer's Linear Algorithm): the letters recorded on unwinding are exactly the tour read in reverse, and reversing a cyclic Euler tour is a cyclic Euler tour. That is why no explicit reversal is needed when only the cyclic sequence matters.
#Prefer the greedy (FKM) version
There is a slicker construction whose output is the lexicographically smallest sequence: the Lyndon-word concatenation (Fredericksen–Kessler–Maiorana). Generate in DFS order all Lyndon words whose length divides n, concatenated:
int k, n; vector<int> a(k * n);
string seq;
void db(int t, int p) { // t = length, p = period
if (t > n && n % p == 0)
for (int i = 1; i <= p; i++) seq.push_back(char('0' + a[i]));
else {
a[t + p] = a[t]; // extend periodically…
db(t + 1, p);
for (int j = a[t] + 1; j < k; j++) { a[t] = j; db(t + 1, t); }
}
}
db(1, 1);Same O(kn) output size, constant memory beyond the array, and it needs no graph at all — a nice example of "the graph was in your head the whole time".
What these are good for
- combination locks / brute force: to try all 4-digit PINs on a wheel you need 104 + 3 turns, not 4 · 104 — a de Bruijn sequence B(10,4), linear instead of k-times linear,
- DNA sequencing / assembly: reads are exactly k-mers, and the overlap graph is a de Bruijn graph — real genome assemblers (SPAdes and descendants) build and simplify de Bruijn graphs, and "contig = Eulerian path after compressing degree-2 chains",
- testing: any kn-long test stream hits every length-n configuration exactly once (registers, sequences, card tricks),
- lower bounds: the argument "windows ↔ edges" proves the length bound and the construction at the same time.
A linear string containing all kn words needs kn + n - 1 characters (take the cyclic sequence and repeat its first n-1 symbols at the end). Problems that ask for "a string" rather than "a cyclic string" are asking for that +n-1; forgetting it is a wrong answer, not an off-by-one style issue.