Re: Permutations (and optimisations)

[Ramprasad A Padmanabhan]

Good effort.
But I use *Algorithm::Permute* 
<http://search.cpan.org/author/EDPRATOMO/Algorithm-Permute-0.06/Permute.pm>

Thanks
Ram
Robin wrote:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Hey, I have written a function that maybe others will find useful to play 
with. It takes a list and then calls a specified function on that list. I'm 
wondering if anyone knows of anything to optimise the code, as there are a 
few list copies going on that allocate/deallocate many times. Is this a 
problem, or is Perl pretty smart about it?

(to be clearer, given a list ('a','b','c') it will call the function many 
times, each time giving one of: ('a','b','c'), ('a','c','b), ('b','a','c'),
('b','c','a'), ('c','a','b') and ('c','b','a'). It also prints progress on 
stderr, but that is more for my own benefit)

It can be called with something like:
permute { push @result, [EMAIL PROTECTED] } @inputList;
if you want to build a list of all the results in @result.
The function is:
# This function takes a list of values, and calls a referenced
# function on each permutation of the list. The first argument is the
# function, the second is the list (there is a third argument used
# internally only.) Note that there are going to be a lot of
# combinations, n!, where n is the number of items in the list.
sub permute(&\@;\@) {
   my $func = shift();
   my @srcList = @{ shift() };
   my @dstList;
   if (@_) {
       @dstList = @{ shift() };
   }
   if (@srcList) {
       # Copy the srcList, pop an entry off the copy, recurse with that
       # appended to the dstList.
       my @srcCopy = @srcList;
       while (@srcCopy) {
           if ([EMAIL PROTECTED]) {
               print STDERR @srcCopy."/"[EMAIL PROTECTED]"\n";
           }
           my $value = pop(@srcCopy);
           # Make another copy of srcList, and remove only the one that
           # we are moving. This copy will be passed on to the next
           # iteration.
           my @srcCopy2 = @srcList;
           splice(@srcCopy2, scalar @srcCopy, 1);
           my @tList = (@dstList, $value);
           permute(\&$func, @srcCopy2, @tList);
       }
   } else {
       # base case
       &$func(@dstList);
   }
}
- -- 
Robin <[EMAIL PROTECTED]>             JabberID: <[EMAIL PROTECTED]>

Hostes alienigeni me abduxerunt. Qui annus est?
PGP Key 0x776DB663 = DD10 5C62 1E29 A385 9866 0853 CD38 E07A 776D B663
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
iD8DBQFA88QJzTjgendttmMRAkCvAJ0Vsy9oPCCU0AQJngntWojFR4ZymQCcDrIQ
7+vi4wbRFzMrELWdipAZoQw=
=Xhei
-----END PGP SIGNATURE-----
 


--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
<http://learn.perl.org/> <http://learn.perl.org/first-response>