A little silliness and a very crude Perl program.
It all started innocently enough. Greg joins #rdfig and says “monring”:
1 <GregElin> | monring
2 <balbinus> | mroinng
3 <ndw> | morinng
4<Talliesin> | mornnigA brief debate ensues about how many possibilities there are. The guesses range from 25 to 120. The answer is 60:
1minnorg
2minnrog
3minonrg
4minorng
5minrnog
6minrong
7mionnrg
8mionrng
9miornng
10mirnnog
11mirnong
12mironng
13mninorg
14mninrog
15mnionrg
16mniorng
17mnirnog
18mnirong
19mnniorg
20mnnirog
21mnnoirg
22mnnorig
23mnnriog
24mnnroig
25mnoinrg
26mnoirng
27mnonirg
28mnonrig
29mnoring
30mnornig
31mnrinog
32mnriong
33mnrniog
34mnrnoig
35mnroing
36mnronig
37moinnrg
38moinrng
39moirnng
40moninrg
41monirng
42monnirg
43monnrig
44monring
45monrnig
46morinng
47morning
48mornnig
49mrinnog
50mrinong
51mrionng
52mrninog
53mrniong
54mrnniog
55mrnnoig
56mrnoing
57mrnonig
58mroinng
59mroning
60mronnigActually, I think the answer is 59. I don’t think “morning” should count.
I built that list with a very crude Perl script:
1@c1 = ('o', 'r', 'n', 'i', 'n');
2
3my %uniq = (); # the n's are not distinct, use a hash to get rid of "dups"
4
5for my $p1 (0..4) {
6 for my $p2 (0..4) {
7 next if $p2 == $p1;
8 for my $p3 (0..4) {
9 next if $p3 == $p1 || $p3 == $p2;
10 for my $p4 (0..4) {
11 next if $p4 == $p1 || $p4 == $p2 || $p4 == $p3;
12 for my $p5 (0..4) {
13 next if $p5 == $p1 || $p5 == $p2 || $p5 == $p3 || $p5 == $p4;
14 $uniq{"m" . $c1[$p1].$c1[$p2].$c1[$p3].$c1[$p4].$c1[$p5] . "g"} = 1;
15 }
16 }
17 }
18 }
19}
20
21foreach my $word (sort keys %uniq) {
22 print "$word\n";
23}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;