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