Good morning kata

brian_d_foy on 2004-08-26T17:32:29

Ziggy pointed me towards a kata for today, by Norman Walsh. He wants to count the permutations of the middle letters in "morning".

I decided to use a module by Tom Phoenix:

use List::Permutor;
  
my $p = List::Permutor->new( split //, 'ornin' );
  
while( my @s = $p->next ) 
	{
	$hash{ join '', 'm', @s, 'g' }++;
	}
	
$, = "\n";
print keys %hash;

---

Permuting by hand

ziggy on 2004-08-26T18:22:02

I decided to take a more manual approach, just to make sure the recursive lobes of my brain still work:

sub cycle {
    my @chars = @_;
    my @result;

    ## Simple case -- only one choice
    return $chars[0] if (@chars == 1);

    for (1..@chars) {
        my $char = shift(@chars);
        push @result, "$char$_" for (cycle(@chars));
        push(@chars, $char);
    }

    return @result;
}

my %words;
$words{"m${_}g"}++ for cycle(qw(o r n i n));

print "$_\n" for sort keys %words;

get count analytically

jmm on 2004-08-27T14:17:44

If, as stated, you just want the count and don't need to see the actual permutations spelled out, it is just a matter of simple arithmetic. The number of permutations of n unique objects is n!. If there are duplicate objects amongst the n, that number must be divided by k(i)! where k(i) is the number of identical objects for the i'th unique item. (That sounds complicated, but for "ornin" the number is 5!/(1!1!2!1!) since there is 1 o, 1 r, 2 n's, and 1 i. So, 120/(1x1x2x1) = 60. If the original word had been morfing and you were permuting orfin it would be 120 (5!/(1!1!1!1!1!)) and if the original word was mooooog you find that there is only one permutation of ooooo (5!/5!).)

sub count_mid_perms {
    my @letters = split //, $_[0];
    pop @letters;
    shift @letters;
    return count_perms \@letters;
}

sub count_perms {
    my $count = 1;
    my $index = 0;
    my %freq;

    foreach my $letter (@_) {
        $count *= ++$index;
        $count /= ++$freq{$letter};
    }
    return $count;
}

Note that the multiplications and divisions in this code is arranged so that to as much an extent as possible (almost) the divisions are used to keep the running value of $count as small as possible but still an integer. Keeping it small reduces the chance that it will overflow the size of the largest integer that can be exactly represented; keeping it integer avoids floating point inaccuracy from rounding errors.