And for completeness, the glob solution, which spends more code fixing up the output than actually generating the results:

sub qm {
    my ($glob) = @_;
    my @rv;
    $glob =~ s/(\w+)/{$1,}/g;

    for my $combo (glob($glob))
    {
        $combo =~ s/^:+//;
        next unless length($combo);
        push @rv, join ':', split /:+/, $combo;
    }

    return @rv;
}
[download]

and is horribly slow as well.

BTW, it's interesting to note the change in benchmark results when the input is a long list of null strings:

$source = ':'x20;
[download]