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.)

  • I can think of the following idea of brute-force algorithm. To list all ternary strings of length 3 (there should be $3^3=27$ of them). We can compute all possibilities of orderings of those strings. For each ordering we paste them together eliminating repeted digits, for example: $012 + 222 = 01222$ and $001 +012 = 0012 $. By doing this for all orderings we might then see which one is the sortest one. Am I understanding your problem in the correct way?. – Mauricio G Tec Sep 7 '13 at 19:35
  • Yet $27!$ seems not very practical.... – Mauricio G Tec Sep 7 '13 at 19:42
up vote 2 down vote accepted

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

For example: $00010020110120210221112122200$

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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