Shortest string containing all fixed-length substrings

Question

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?!

Answer 1

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.

Answer 2

De Bruijn sequences are polytime computable. You can find a discussion of algorithms for generating them in a question I asked at StackOverflow.