perlfaq4: How do I permute N elements of a list?

* 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)?