* completely replaced answer with one from Joe Schaefer.
+ emphasis module use (the XS versions are *really* fast)
+ show a pure perl function that is still 5 times faster than
the previous example
localhost_brian[2997]$ cvs diff -u -d !$
cvs diff -u -d perlfaq4.pod
Index: perlfaq4.pod
===================================================================
RCS file: /cvs/public/perlfaq/perlfaq4.pod,v
retrieving revision 1.33
diff -u -d -r1.33 perlfaq4.pod
--- perlfaq4.pod 8 Oct 2002 08:05:50 -0000 1.33
+++ perlfaq4.pod 10 Oct 2002 23:23:25 -0000
@@ -1460,34 +1460,40 @@
=head2 How do I permute N elements of a list?
-Here's a little program that generates all permutations
-of all the words on each line of input. The algorithm embodied
-in the permute() function should work on any list:
+Use the List::Permutor module on CPAN. If the list is
+actually an array, try the Algorithm::Permute module (also
+on CPAN). It's written in XS code and is very efficient.
- #!/usr/bin/perl -n
- # tsc-permute: permute each word of input
- permute([split], []);
- sub permute {
- my @items = @{ $_[0] };
- my @perms = @{ $_[1] };
- unless (@items) {
- print "@perms\n";
- } else {
- my(@newitems,@newperms,$i);
- foreach $i (0 .. $#items) {
- @newitems = @items;
- @newperms = @perms;
- unshift(@newperms, splice(@newitems, $i, 1));
- permute([@newitems], [@newperms]);
- }
+ use Algorithm::Permute;
+ my @array = 'a'..'d';
+ my $p_iterator = Algorithm::Permute->new ( \@array );
+ while (my @perm = $p_iterator->next) {
+ print "next permutation: (@perm)\n";
}
- }
-Unfortunately, this algorithm is very inefficient. The Algorithm::Permute
-module from CPAN runs at least an order of magnitude faster. If you don't
-have a C compiler (or a binary distribution of Algorithm::Permute), then
-you can use List::Permutor which is written in pure Perl, and is still
-several times faster than the algorithm above.
+Here's a little program that generates all permutations of
+all the words on each line of input. The algorithm embodied
+in the permute() function is discussed in Volume 4 (still
+unpublished) of Knuth's _The Art of Computer Programming_
+and will work on any list:
+
+ #!/usr/bin/perl -n
+ # Fischer-Kause ordered permutation generator
+
+ sub permute (&@) {
+ my $code = shift;
+ my @idx = 0..$#_;
+ while ( $code->(@_[@idx]) ) {
+ my $p = $#idx;
+ --$p while $idx[$p-1] > $idx[$p];
+ my $q = $p or return;
+ push @idx, reverse splice @idx, $p;
+ ++$q while $idx[$p-1] > $idx[$q];
+ @idx[$p-1,$q]=@idx[$q,$p-1];
+ }
+ }
+
+ permute {print"@_\n"} split;
=head2 How do I sort an array by (anything)?
