faster permute() for perlfaq4

I wrote a permute() function that's faster than the one in the FAQ (and I
think is more understandable).  It's still a divide-and-conquer approach,
obviously, but it's got much better speed.

I've yet to compare it to Algorithm::Permute.

I should probably write it in C instead of Perl.

#!/usr/bin/perl

use Benchmark 'timethese';
use strict;

my $str = shift || "abcdef";

timethese(-5, {
  tchrist => sub { tom_permute([split //, $str], []) },
  japhy   => sub { japhy_permute(split //, $str) },
});


sub tom_permute {
  my @items = @{ $_[0] };
  my @perms = @{ $_[1] };
  unless (@items) { }
  else {
    my(@newitems,@newperms,$i);
    foreach $i (0 .. $#items) {
      @newitems = @items;
      @newperms = @perms;
      unshift(@newperms, splice(@newitems, $i, 1));
      tom_permute([@newitems], [@newperms]);
    }
  }
}


{
  my (%found,$str);

  sub japhy_permute {
    %found = ();
    permute_recurse(split //, shift);
    return keys %found;
  }

  sub permute_recurse {
    for (1 .. @_) {
      push @_, shift;
      $str .= $_[-1];
      @_ == 1 ? $found{$str}++ : permute_recurse(@_[0..$#_-1]);
      chop $str;
    }
  }
}

-- 
Jeff "japhy" Pinyan     japhy@pobox.com     http://www.pobox.com/~japhy/
PerlMonth - An Online Perl Magazine            http://www.perlmonth.com/
The Perl Archive - Articles, Forums, etc.    http://www.perlarchive.com/
CPAN - #1 Perl Resource  (my id:  PINYAN)        http://search.cpan.org/

• faster permute() for perlfaq4 by Jeff Pinyan
• Re: faster permute() for perlfaq4 by Jeff Pinyan