5
$\begingroup$

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

$\endgroup$
29
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ lovely application! :) $\endgroup$ – Sasho Nikolov Jul 1 '11 at 16:27
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.