## 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: ,