in reply to Re: Sorting characters within a string
in thread Sorting characters within a string

I think you're right that it would be more work initially for the "all possibilites" hash. I'm no mathematician/statistican but I think there are more like 5! = 120 possibilities (and I certainly wouldn't want to build that hash by hand). Tilly, you're a mathematician. What are the correct number of possibilities?

Building the hash programmatically would be an interesting brain teaser.

Update: This was assuming string lengths of up to 5.

If the code and the comments disagree, then both are probably wrong. -- Norm Schryer

  • Comment on Re: Re: Sorting characters within a string

Replies are listed 'Best First'.
Re (tilly) 3: Sorting characters within a string
by tilly (Archbishop) on Aug 24, 2001 at 06:02 UTC
    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]
[reply]
[d/l]
[select]
Re: Re: Re: Sorting characters within a string
by guillaume (Pilgrim) on Aug 24, 2001 at 05:45 UTC
    Building the hash programmatically would be ani nteresting brain teaser.

    Here is the worst way to do it:
    my @strings = (grep /[acgmt]{2}/, ('aa' .. 'tt'), 
               grep /[acgmt]{3}/, ('aaa' .. 'ttt'), 
               grep /[acgmt]{4}/, ('aaaa' .. 'tttt'));

my %sort_cache;

for my $key (@strings) {
    $sort_cache{$key} = join '',sort split('',$key);
}

    [download]

    Hey, don't take this seriously ;-) it does the job but it's so inefficient it's scary.
    Guillaume
[reply]
[d/l]
      Guillaume,

      I think one of the assumptions (although not clearly stated) is that no string has repeated characters in it.

      Very inventive code though!

      Update: Maybe a regexp to eliminate any string with duplicate letters. As though things weren't bad enough :)

      If the code and the comments disagree, then both are probably wrong. -- Norm Schryer

[reply]
Re: Re: Re: Sorting characters within a string
by jlongino (Parson) on Aug 24, 2001 at 05:33 UTC
    Boy, I really suck at this. One more try assuming strings of length 2-4:

    length of 2: 5 . 4 = 20
    length of 3: 5 . 4 . 3 = 60
    length of 4: 5 . 4 . 3 . 2 = 120
    total of 20 + 60 + 120 = 200 possibilities.

    If the code and the comments disagree, then both are probably wrong. -- Norm Schryer

[reply]

In Section Seekers of Perl Wisdom