All pairs of letters (de Bruijn sequence with $n=2,k=52$)

combinatorics

Suppose I’m designing a font and want to verify its kerning.

Ignoring punctuation, I want to generate a string made of $52$ symbols (uppercase A to Z and lowercase a to z), so that all possible letter pairs occur at least once.

I looked up similar problems, and it seems that what I want is a de Bruijn sequence. However, I couldn’t find anything online relating to an alphabet size $k>9$.

How long would my de Bruijn sequence be, and how would I go about generating said sequence?


Solution 1:

For $n=2$, such sequences are trivial to create. Begin with 'zA' and continually append the lowest value that completes a previously unseen pair:

zAABACAD...AxAyAzBBCBDBE...BxByBzCCDCECF....wwxwywzxxyxzyyzzA

Related

Minimal spanning set ("conical basis") for 2x2 Hermitian PSD (positive semi-definite) cone?
$S^1$-valued function on $T^n$
Finding all polynomials $P(x) \in \mathbb R[x]$ such that $P(x)^2=4P\left(x^2-5x+1\right)+2$
$[0,1]\cap\mathbb{Q}$ is not compact in $\mathbb{Q}$
$f:X \to Y $ is continuous on $X$ and $(X, d_1) $ is compact. Then $f:X\to Y$ is uniformly continuous on $X$
Relationship between different Gödel Sentences
An elementary identical equation
question about decomposition of positive terms series $\sum_{n=1}^\infty a_k$ where $a_k=b_k + c_k$
Simplifying $\frac{\omega\sin(\omega t)\tan(\omega{t})+\omega(\cos(\omega t)+1)\sec^2(\omega t)}{(\cos(\omega t) +1)^2}$
Proof that a nonzero point is continuous for g(x)
Finding all functions $f:\mathbb{R}\to\mathbb{R}$ such that $f\bigl(xf(x+y)\bigr)=f\bigl(yf(x)\bigr)+x^2$
Notation of derivative w.r.t. the multi-variable function argument of an univariate function