Good M{o,r,n,i,n}g

Volume 7, Issue 153; 26 Aug 2004; last modified 08 Oct 2010

A little silliness and a very crude Perl program.

It all started innocently enough. Greg joins #rdfig and says “monring”:

 <GregElin> | monring
 <balbinus> | mroinng
      <ndw> | morinng
<Talliesin> | mornnig

A brief debate ensues about how many possibilities there are. The guesses range from 25 to 120. The answer is 60:

minnorg
minnrog
minonrg
minorng
minrnog
minrong
mionnrg
mionrng
miornng
mirnnog
mirnong
mironng
mninorg
mninrog
mnionrg
mniorng
mnirnog
mnirong
mnniorg
mnnirog
mnnoirg
mnnorig
mnnriog
mnnroig
mnoinrg
mnoirng
mnonirg
mnonrig
mnoring
mnornig
mnrinog
mnriong
mnrniog
mnrnoig
mnroing
mnronig
moinnrg
moinrng
moirnng
moninrg
monirng
monnirg
monnrig
monring
monrnig
morinng
morning
mornnig
mrinnog
mrinong
mrionng
mrninog
mrniong
mrnniog
mrnnoig
mrnoing
mrnonig
mroinng
mroning
mronnig

Actually, I think the answer is 59. I don’t think “morning” should count.

I built that list with a very crude Perl script:

@c1 = ('o', 'r', 'n', 'i', 'n');

my %uniq = (); # the n's are not distinct, use a hash to get rid of "dups"

for my $p1 (0..4) {
    for my $p2 (0..4) {
	next if $p2 == $p1;
	for my $p3 (0..4) {
	    next if $p3 == $p1 || $p3 == $p2;
	    for my $p4 (0..4) {
		next if $p4 == $p1 || $p4 == $p2 || $p4 == $p3;
		for my $p5 (0..4) {
		    next if $p5 == $p1 || $p5 == $p2 || $p5 == $p3 || $p5 == $p4;
		    $uniq{"m" . $c1[$p1].$c1[$p2].$c1[$p3].$c1[$p4].$c1[$p5] . "g"} = 1;
		}
	    }
	}
    }
}

foreach my $word (sort keys %uniq) {
    print "$word\n";
}

Can anyone think of a better way?

Let’s just leave the question of whether or not this exercise was worth the time unanswered, ok?

Comments

There are 5 places to put the o. Then there are 4 places left to put the r. Then there are 3 places left to put the i. The remaining 2 places are filled with n.

5 x 4 x 3 = 60

—Posted by Sjoerd Visscher on 26 Aug 2004 @ 06:02 UTC #

There's a recipe [1] in the online Python Cookbook to calculate permutations and combinations of elements in a list, using Python's generators. You'll need to remove duplicates from the results, since the two n's are perceived as different tokens; but you'll eventually end up with 60 possibilities.

[1] http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465

—Posted by Giulio Piancastelli on 26 Aug 2004 @ 11:14 UTC #

Sjoerd: All mathmatical formulas must be proven with long, inefficient, brute force Perl algorithms. -grin-

—Posted by Jay Hannah on 26 Aug 2004 @ 11:36 UTC #

See http://www.oreillynet.com/pub/wlg/5492 for brian d foy's generic solution.

—Posted by martin english on 27 Aug 2004 @ 01:32 UTC #

No need to reinvent the wheel:

use Algorithm::FastPermute ('permute');
my @letters = qw/o r n i n/;
my %seen;
permute {
my $word = join "", "m", @letters, "g";
print "$word\n" unless $seen{$word}++;
} @letters;
—Posted by Tony Bowden on 28 Aug 2004 @ 10:14 UTC #