Permutations

Now that we are starting to get settled in to our new house, I’ve been meaning to write a progress report on the Numerics grant. This, however, is not that post. Instead it details a quick side project I’ve just done for $work. I don’t reckon I can bill them for this bit, but at least I can get a post out of it, and it definitely is helping with my debugging.

So, I needed to do permutations for a test. The following code is a pretty straightforward port of one of the solutions from HOP:

sub pattern_to_permutation(@pattern, @items1) { 
    my @items = @items1;
    my @r;
    for @pattern {
        push @r, @items.splice($_, 1);
    } 
    @r; 
}

sub n_to_pat($n is copy, $length) { 
    my @odometer; 
    for 1 .. $length -> $i { 
        unshift @odometer, $n % $i; 
        $n div= $i; 
    } 
    return $n ?? () !! @odometer; 
}

sub permute(@items) { 
    my $n = 0;
    gather loop {
        my @pattern = n_to_pat($n++, +@items);
        last unless ?@pattern;
        take pattern_to_permutation(@pattern, @items); 
    }
}

If you compare it to the original code (which itself is very pretty) on pages 131-134, this version is 14% shorter and I would argue somewhat clearer as well, thanks to the nice features of Perl 6. It also uses Perl 6′s native gather / take construct to make a lazy iterator, rather than needing HOP’s iterator code. (Note that the ugly @items = @items1 hack is a workaround for a Rakudo-bug.)

I am inclined to think that permute might belong in Perl 6′s core. If not, this code shows that it is fairly easy to implement. (That said, I have not come close to exhaustively testing this code.)

About these ads

Tags: Perl 6, Permutations