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.)
Tags: Perl 6, Permutations
Leave a Reply