Algorithm::Permute(3pm) | User Contributed Perl Documentation | Algorithm::Permute(3pm) |
Algorithm::Permute - Handy and fast permutation with object oriented interface
use Algorithm::Permute; # default is to create n of n objects permutation generator my $p = Algorithm::Permute->new(['a'..'d']); # but also you can create r of n objects permutation generator, where r <= n my $p = Algorithm::Permute->new([1..4], 3); while (my @res = $p->next) { print join(", ", @res), "\n"; } # and this one is the speed demon: my @array = (1..9); Algorithm::Permute::permute { print "@array\n" } @array;
This handy module makes performing permutation in Perl easy and fast, although perhaps its algorithm is not the fastest on the earth. It supports permutation r of n objects where 0 < r <= n.
Starting with version 0.03, there is a function - not exported by default - which supports a callback style interface:
You have to pass an array, it can't just be a list. It does work with special arrays and tied arrays, though unless you're doing something particularly abstruse you'd be better off copying the elements into a normal array first. Example:
my @array = (1..9); permute { print "@array\n" } @array;
The code is run inside a pseudo block, rather than as a normal subroutine. That means you can't use "return", and you can't jump out of it using "goto" and so on. Also, "caller" won't tell you anything helpful from inside the callback. Such is the price of speed.
The order in which the permutations are generated is not guaranteed, so don't rely on it.
The low-level hack behind this function makes it currently the fastest way of doing permutation among others.
I've collected some Perl routines and modules which implement permutation, and do some simple benchmark. The whole result is the following.
Permutation of eight scalars:
Abigail's : 9 wallclock secs ( 8.07 usr + 0.30 sys = 8.37 CPU) Algorithm::Permute : 5 wallclock secs ( 5.72 usr + 0.00 sys = 5.72 CPU) Algorithm::Permute qw(permute): 2 wallclock secs ( 1.65 usr + 0.00 sys = 1.65 CPU) List::Permutor : 27 wallclock secs (26.73 usr + 0.01 sys = 26.74 CPU) Memoization : 32 wallclock secs (32.55 usr + 0.02 sys = 32.57 CPU) perlfaq4 : 36 wallclock secs (35.27 usr + 0.02 sys = 35.29 CPU)
Permutation of nine scalars (the Abigail's routine is commented out, because it stores all of the result in memory, swallows all of my machine's memory):
Algorithm::Permute : 43 wallclock secs ( 42.93 usr + 0.04 sys = 42.97 CPU) Algorithm::Permute qw(permute): 15 wallclock secs ( 14.82 usr + 0.00 sys = 14.82 CPU) List::Permutor : 227 wallclock secs (226.46 usr + 0.22 sys = 226.68 CPU) Memoization : 307 wallclock secs (306.69 usr + 0.43 sys = 307.12 CPU) perlfaq4 : 272 wallclock secs (271.93 usr + 0.33 sys = 272.26 CPU)
The benchmark script is included in the bench directory. I understand that speed is not everything. So here is the list of URLs of the alternatives, in case you hate this module.
In Edwin's words: Yustina Sri Suharini - my ex-fiance-now-wife, for providing the permutation problem to me.
Edwin Pratomo <edpratomo@cpan.org> was the original author.
Stephan Loyd <sloyd@cpan.org> is co-maintainer after version 0.12.
The object oriented interface is taken from Tom Phoenix's "List::Permutor". Robin Houston <robin@kitsite.com> invented and contributed the callback style interface.
This software is copyright (c) 1999 by Edwin Pratomo.
This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.
2018-11-02 | perl v5.28.0 |