<p>De Bruijn sequences are polytime computable. You can find a discussion of algorithms for generating them in a question I asked at <a href="https://stackoverflow.com/questions/4008603/how-to-compute-de-bruijn-sequences-for-non-power-of-two-sized-alphabets">StackOverflow</a>.</p>

CC BY-SA 3.0
2011-07-21T12:00:43.533Z
2011-07-21T12:00:43.533Z
2017-05-23T12:40:09.333Z
uckelman
<p>This is called a de Bruijn sequence ( <a href="http://en.wikipedia.org/wiki/De_Bruijn_sequence">http://en.wikipedia.org/wiki/De_Bruijn_sequence</a> ).  You can generate it by taking an Euler tour of a de Bruijn graph, but there are also other ways.  You can use de Bruijn sequences to break into 1990s-era cars efficiently ( <a href="http://everything2.com/title/Weak+security+in+our+daily+lives">http://everything2.com/title/Weak+security+in+our+daily+lives</a> ) among many other applications. </p>

CC BY-SA 3.0
2011-07-01T16:27:03.903Z
lovely application! :)
Sasho Nikolov
CC BY-SA 3.0
2011-07-01T04:36:12.303Z
2011-07-01T04:36:12.303Z
Peter Boothe
<p>This is related to a math.SE question I asked, but I've realized I want a slightly different form and it's probably more of an algorithms question.</p>

<p>Fix an alphabet $\Sigma$.  Let $P(n)$ be all length-$n$ strings over $\Sigma$.  What is the shortest string $S$ such that every $s \in P(n)$ is a substring of $S$?</p>

<p>For example, let $\Sigma = \{a\}$ and $n=1$; then clearly $S=a$ is minimal.  If instead $\Sigma = {a,b}$ and $n=2$, $P(2) = {aa, ab, ba, bb}$ and $S = aabba$ is minimal.</p>

<p>Clearly we are solving "shortest common superstring" over $P(n)$, and it's known to be MaxSNP hard. I'm wondering if this special form, with $P(n)$ containing all substrings of $\Sigma$ might be easy?!</p>

<ds.algorithms><co.combinatorics><fl.formal-languages>
Shortest string containing all fixed-length substrings
Fixee
# Shortest string containing all fixed-length substrings

(Asked by: username_0 on 2011-07-01)

This is related to a math.SE question I asked, but I've realized I want a slightly different form and it's probably more of an algorithms question.

Fix an alphabet $\Sigma$. Let $P(n)$ be all length-$n$ strings over $\Sigma$. What is the shortest string $S$ such that every $s \in P(n)$ is a substring of $S$?

For example, let $\Sigma = \{a\}$ and $n=1$; then clearly $S=a$ is minimal. If instead $\Sigma = {a,b}$ and $n=2$, $P(2) = {aa, ab, ba, bb}$ and $S = aabba$ is minimal.

Clearly we are solving "shortest common superstring" over $P(n)$, and it's known to be MaxSNP hard. I'm wondering if this special form, with $P(n)$ containing all substrings of $\Sigma$ might be easy?!

**Tags:** ds.algorithms, co.combinatorics, fl.formal-languages

---

## 2 answers

### Answer by username_2 on 2011-07-01. Score: 29 | Accepted answer

This is called a de Bruijn sequence ( <http://en.wikipedia.org/wiki/De_Bruijn_sequence> ). You can generate it by taking an Euler tour of a de Bruijn graph, but there are also other ways. You can use de Bruijn sequences to break into 1990s-era cars efficiently ( <http://everything2.com/title/Weak+security+in+our+daily+lives> ) among many other applications.

> **Comments:**
> **username_3**: lovely application! :)  

---

### Answer by username_1 on 2011-07-21. Score: 3

De Bruijn sequences are polytime computable. You can find a discussion of algorithms for generating them in a question I asked at [StackOverflow](https://stackoverflow.com/questions/4008603/how-to-compute-de-bruijn-sequences-for-non-power-of-two-sized-alphabets).


---

