Shortest ternary string containing all ternary strings of length 3?

Question

How can we find/construct the shortest ternary string that contains all ternary strings of length 3? For instance, $120011$ contains $120$, $200$, $001$, and $011$.

(The shortest such a string could possibly be is 29 digits long, as we would have one digit for each 3 digit string, and the last trailing 2 digits for the final 3 digit substring represented.)

Answer 1

What you're looking for is essentially a De Bruijin sequence.

For example: $00010020110120210221112122200$

Answer 2

Here is a little Perl program, mostly self-explanatory, that prints the first $k$ such sequences. (Can be simplified by removing the error-checking code.)

#! /usr/bin/perl -w

sub nxt {
    my ($str, $rep, $n, $cref, $max) = @_;

    if($n == 27){
      my %verify = ();

      for(my $pos=0; $pos<27; $pos++){
          $verify{substr($str, $pos, 3)} = 1;
      }

      print $str; print " "; 
      print scalar(keys %verify); print "\n";

      $$cref++;
      exit 0 if $$cref == $max;

      return;
    }

    my $sfx = substr $str, -2;
    foreach my $digit ("0", "1", "2"){
      my $item = $sfx . $digit;

      if(not exists($rep->{$item})){
          $rep->{$item} = 1;
          nxt($str . $digit, $rep, $n+1, $cref, $max);
          delete $rep->{$item}; 
      }
    }
}

MAIN: {
    my $max = shift || 10;
    die "positive value for count please" if $max<1;

    my $count = 0;
    nxt("000", {"000" => 1}, 1, \$count, $max);
}

The output looks like this.

00010020110120210221112122200 27
00010020110120210221211122200 27
00010020110120210222111212200 27
00010020110120210222121112200 27
00010020110120211121022122200 27
00010020110120211121022212200 27
00010020110120211121221022200 27
00010020110120211121222102200 27
00010020110120211122121022200 27
00010020110120211122212102200 27
00010020110120212102211122200 27
00010020110120212102221112200 27
00010020110120212111221022200 27
00010020110120212111222102200 27
00010020110120212211121022200 27
00010020110120212221112102200 27