The most elegant algorithms count up in base N (where N is the length of the list), and map that representation back to the original list. Since counting in base N wasn't the natural way for me to think about the problem, I decided to count in decimal and then convert it to the base N. TMTOWTDI, and all that. :-)

I had been writing all this code in Perl, but the Other Guy was using Python. I thought, "hey, I'm flexible. I'll just port it from Perl to Python." It was a surprisingly simple port. Perhaps the code doesn't look perfectly Pythonic, but it works as advertised, and made me happy.

Then I started playing with Pugs, and thought, "hey, this is fun. I'll port it from Perl to Perl 6." Of course, in doing this I uncovered a few bugs in Pugs, and ended up writing and committing failing test cases for those bugs (which were apparently fixed 2 days later, as the tests stopped failing and the code started working as advertised).

At the end of this adventure, I decided to share it with the Monks. So here it is, and for those who are dying to see, here's all three versions of the code. First, the original Perl 5 implementation:

#!/usr/bin/perl
use strict;
use warnings;

my %digit_letters = (
    2 => [qw(a b c)],
    3 => [qw(d e f)],
    4 => [qw(g h i)],
    5 => [qw(j k l)],
    6 => [qw(m n o)],
    7 => [qw(p r s)],
    8 => [qw(t u v)],
    9 => [qw(w x y)],
);

my @letter_combinations;

my $letterchooser = choose([0 .. 2], 4);
while (my $letters = $letterchooser->()) {
    push @letter_combinations, $letters;
}

my $digitchooser = choose([2 .. 9], 4);
while (my $digits = $digitchooser->()) {
    for my $letters (@letter_combinations) {
        my @digits  = split //, $digits;
        my @letters = split //, $letters;

        my @word = map { $digit_letters{$digits[$_]}[$letters[$_]] }
                   0 .. $#digits;

        print "$digits: ", @word, "\n";
    }
}

sub basen {
    my ($base, $num) = @_;

    my $q = int($num / $base);
    my $r =     $num % $base;

    return $r if $q == 0;
    return basen($base, $q), $r;
}

sub choose {
    my ($list, $number) = @_;

    my $listcount = @$list;
    my $combcount = @$list**$number;

    my $curr = 0;

    sub {
        return if $curr >= $combcount;

        my @choice = basen($listcount, $curr++);
        unshift @choice, 0 while @choice < $number;

        return join "", map $list->[$_], @choice;
    }
}
[download]

Next, Python (the output is slightly different, but I didn't feel like wrangling it into shape):

#!/usr/bin/python

def basen (base, num):
    q = num / base
    r = num % base

    if q == 0:
        return [r]
    else:
        return basen(base, q) + [r]

def choose (list, number):
    iterations = len(list)**number

    for i in range(0, iterations):
        choice = basen(len(list), i)

        while len(choice) < number:
            choice.insert(0, 0)

        yield [ list[x] for x in choice ]

digit_letters = { 2: [ 'a', 'b', 'c' ],
                  3: [ 'd', 'e', 'f' ],
                  4: [ 'g', 'h', 'i' ],
                  5: [ 'j', 'k', 'l' ],
                  6: [ 'm', 'n', 'o' ],
                  7: [ 'p', 'r', 's' ],
                  8: [ 't', 'u', 'v' ],
                  9: [ 'w', 'x', 'y' ] }

letter_choices = []

for letters in choose([0,1,2], 4):
    letter_choices.append(letters)

for digits in choose(range(2,10), 4):
    for letters in letter_choices:
        word = []

        for i in range(0, len(digits)):
            digit    = digits[i]
            letter_i = letters[i]
            letter   = digit_letters[digit][letter_i]

            word.append(letter)

        print digits, ":", ''.join(word)
[download]

And finally, the Perl 6 version:

#!/usr/bin/pugs

my %digit_letters = (
    2 => [qw(a b c)],
    3 => [qw(d e f)],
    4 => [qw(g h i)],
    5 => [qw(j k l)],
    6 => [qw(m n o)],
    7 => [qw(p r s)],
    8 => [qw(t u v)],
    9 => [qw(w x y)],
);

my @letterchoices;

my $letters;
my $letterchooser = choose([0 .. 2], 4);
while $letters = $letterchooser() {
    push @letterchoices, $letters;
}

my $digits;
my $digitchooser = choose([2 .. 9], 4);
while $digits = $digitchooser() {
    my $letters;
    for @letterchoices -> $letters {
        my @digits  = split '', $digits;
        my @letters = split '', $letters;

        my @word;

        for zip(@digits, @letters) -> $digit, $letter {
            push @word, %digit_letters{$digit}[$letter];
        }

        say "$digits: ", @word;
    }
}

sub basen ($base, $num) {
    my $q = int($num / $base);
    my $r =     $num % $base;

    return $r if $q == 0;
    return basen($base, $q), $r;
}

sub choose ($list, $number) {
    my $iterations = $list.elems ** $number;
    my $current = 0;

    return sub {
        return if $current >= $iterations;

        my @choice = basen($list.elems, $current++);
        unshift @choice, 0 while @choice.elems < $number;

        return @choice.map({$list[$_]}).join("");
    };
}
[download]

There are a few things I got from this experience. One thing that really stood out was how similar the solutions were. Perhaps that was a consequence of the fact that I was porting the code from one to the next, rather than starting all over, but it shows that the facilities used here are available in all three languages.

Also, I noticed that the Perl 6 version still looks very much like Perl. It just has a few changes, and I think they're for the better. Perhaps the code can be further P6-ified, but I don't think it will change the feel dramatically. I think the new language is going to turn out nicely.

Finally, I noticed that -- yes, I am master of the obvious -- Python does some things that Perl doesn't. The big standout here was the built in iterator support. Just using yield instead of return is a heck of a lot easier than using an anonymous sub that wrangles closures to provide the same functionality. It's not that I would want to get rid of the closures (which seems to be the Python solution), but I'd like to have the easier technique too. Perl is supposed to be the language that steals good ideas from all around, isn't it?

As always, code criticisms/critiques welcome. I'm especially interested in any Perl6ish improvements to that version. I tend to limit myself to things that work in Pugs, but I know there are others here who don't have that limitation, and I'd love to hear from them. Anything else welcome, too! Please reply early and often. :-)