Re: [MacPerl] 2D Permutations

["Ken Williams" <ken@forum.swarthmore.edu>]

Hi David,

I couldn't really Benchmark your module, because running it more than
once seems to trigger an infinite loop.  Anyway, I wrote a simpler
version of what you're doing, see if it makes sense to you.  It's the
same basic idea, using odometer-style listing instead of recursion to
list the permutations.

     package List::Permutor2D;
     # Rolls like an odometer.

     sub new {
       my $pkg = shift;
       return bless {vals => [@_],
                     curr => [(0)x@_],
                     done => 0,
                    }, $pkg;
     }

     sub next {
       my $self = shift;
       return if $self->{done};
       return( (map $self->{vals}[$_][$self->{curr}[$_]],
                   0..$#{$self->{vals}}), $self->incr);
     }

     sub incr {
       my $self = shift;
       $self->{curr}[-1]++;
       foreach (reverse 0..$#{$self->{curr}}) {
         if ($self->{curr}[$_] >= @{$self->{vals}[$_]}) {
           $self->{curr}[$_] = 0;
           $self->{curr}[$_-1]++;
         } else {
           return;
         }
       }
       $self->{done} = 1;
       return;
     }

That incr() method might be simplifiable too.  Didn't work too hard on
trying.

Benchmarking code follows, if you want to fix the loop bug & compare them:

      use Benchmark;
      my @ary = ( [ "A", "B" ],
                  [ "C", "D", "E" ],
                  [ "F", "G", "H" ]
                );
      my @a;
      timethese (1000, {
        old => sub {my $p = List::Permutor2D_old->new(@ary);
                    1 while @a = $p->next},
        new => sub {my $p = List::Permutor2D->new(@ary);
                    1 while @a = $p->next},
      });


diberri@ucla.edu (David J. Iberri) wrote:
>Hi all,
>
>I just finished writing a module that process all permutations in the 2nd
>dimension (only the 2nd) of a 2D array. I'm new at module writing and am
>worried that it's not optimized for speed or efficiency.  I've used it on my
>G3/300, and it seems fine, but I'm still concerned that it's not fast enough
>for the real world.  Any suggestions?

  -------------------                            -------------------
  Ken Williams                             Last Bastion of Euclidity
  ken@forum.swarthmore.edu                            The Math Forum

# ===== Want to unsubscribe from this list?
# ===== Send mail with body "unsubscribe" to macperl-request@macperl.org