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
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
Sjoerd: All mathmatical formulas must be proven with long, inefficient, brute force Perl algorithms. -grin-
See http://www.oreillynet.com/pub/wlg/5492 for brian d foy's generic solution.
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;