Are duplicates allowed? If so then the correct number for 1 is 5, for 2 is 5*5=25, for 3 is 5*5*5=125, and for 4 is 5*5*5*5=625. For all strings of length 2-4 that comes out to a grand total of 775.

Were I autogenerating, my approach might be as follows (untested):

{
  my @c = qw(A T C G N);
  my @strings = @c;
  foreach (1..5) {
    foreach (@strings) {
      $sorted_str{$string} = join '', sort, split //;
    }
    @strings = map {
      my $string = $_;
      map $string.$_, @c;
    } @strings;
  }
}
[download]

Note that the nested map will be much slower than you think if you are pre 5.6.1. Personally I would be inclined to use the Orcish (for "Or Cache") maneuver for this:

  $bases = $sorted{$bases}
    ||= join '', sort, split //, $bases;
[download]