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