view release on metacpan or  search on metacpan

lib/Algorithm/Loops.pm  view on Meta::CPAN

will only print the one line, "3 3 3 3\n", because NextPermute() quickly
determines that there are no other unique permutations.

Try out the demonstration program included in the "ex" subdirectory of
the source distribution of this module:

    > perl ex/Permute.plx tool
    1: loot
    2: loto
    3: ltoo
    4: olot
    5: olto
    6: oolt
    7: ootl
    8: otlo
    9: otol
    10: tloo
    11: tolo
    12: tool

Most permutation generators would have listed each of those twice
(thinking that swapping an "o" with another "o" made a new permutation). 
Or consider:

    > perl ex/Permute.plx noon
    1: nnoo
    2: nono
    3: noon
    4: onno
    5: onon
    6: oonn

Most permutation generators would have listed each of those B<four>
times.

Note that using a hash to eliminate duplicates would require a hash table
big enough to hold all of the (unique) permutations and so would defeat
the purpose of iterating.  NextPermute* does not use a hash to avoid
duplicates.

=item Generated in sorted order

If you were to run code like:


    my @list= sort GetValuesSomehow();
    do {
        print join('',@lista, $/);
    } while(  NextPermute( @list )  );

then the lines output would be sorted (assuming none of the values in
@list contained newlines.  This may be convenient in some corcumstances.

That is, the permutations are generated in sorted order.  The first
permutations have the lowest values at the front of the list.  As you
iterate, larger values are shifted to be in front of smaller values,
starting at the back of the list.  So the value at the very front of the
list will change the fewest times (once for each unique value in the
list), while the value at the very end of the list changes between most
iterations.

=item Fast

If you don't have to deal with duplicate values, then Algorithm::Permute
provides some routines written in C (which makes them harder to install
but about twice as fast to run as the NextPermute* routines) that you can
use.

Algorithm::Permute also includes some fun benchmarks comparing different
Perl ways of finding permutations.  I found NextPermute to be faster than
any of the routines included in those benchmarks except for the ones
written in C that I mentioned above.  Though none of the benchmarked
routines deal with duplicates.

=back

=head3 Notes

Note that NextPermute() considers two values (say $x and $y) to be
duplicates if (and only if) C<$x eq $y>.

NextPermuteNum() considers $x and $y to be duplicates if C<$x == $y>.

If you have a list of floating point numbers to permute, you might want
to use NextPermute() [instead of NextPermuteNum()] as it is easy to end
up with $x and $y that both display the same (say as "0.1") but are
B<just barely> not equal numerically.  Thus $x and $y would I<look> equal
and it would be true that C<$x eq $y> but also true that C<$x != $y>.  So
NextPermute() would consider them to be duplicates but NextPermuteNum()
would not.

For example, $x could be slightly more than 1/10, likely about
0.1000000000000000056, while $y is slightly more at about
0.0999999999999999917 (both of which will be displayed as "0.1" by Perl
and be considered C<eq> (on most platforms):

    > perl -w -Mstrict
    my $x= 0.1000000000000000056;
    my $y= 0.0999999999999999917;
    print "x=$x\ny=$y\n";
    print "are eq\n"   if  $x eq $y;
    print "are ==\n"   if  $x == $y;
    print "are !=\n"   if  $x != $y;
    <EOF>
    x=0.1
    y=0.1
    are eq
    are !=

=head2 NestedLoops

=head3 Introduction

Makes it easy to simulate loops nested to an arbitrary depth.

It is easy to write code like:

    for my $a (  0..$N  ) {
     for my $b (  $a+1..$N  ) {
      for my $c (  $b+1..$N  ) {

lib/Algorithm/Loops.pm  view on Meta::CPAN

        {  OnlyWhen => 1  },
        sub { "@_" },
    );

is similar to:

    my @list= qw/ 1 11 111 112 113 12 121 122 123
                  13 131 132 133 2 21 211 212 ... /;

Another example:

    NestedLoops(
        [  ( [ 1..3 ] ) x 3  ],
        { OnlyWhen => 1 },
        \&Stuff,
    );

is similar to:

    for my $a (  1..3  ) {
        Stuff( $a );
        for my $b (  1..3  ) {
            Stuff( $a, $b );
            for my $c (  1..3  ) {
                Stuff( $a, $b, $c );
            }
        }
    }

Last example:

    NestedLoops(
        [  ( [ 1..3 ] ) x 3  ],
        { OnlyWhen => \&Test },
        \&Stuff,
    );

is similar to:

    for my $a (  1..3  ) {
        Stuff( $a )   if  Test( $a );
        for my $b (  1..3  ) {
            Stuff( $a, $b )   if  Test( $a, $b );
            for my $c (  1..3  ) {
                Stuff( $a, $b, $c )
                    if  Test( $a, $b, $c );
            }
        }
    }

=back

=head4 \&Code

The subroutine that gets called for each iteration.

=head4 Iterator

If you don't pass in a final code reference to NestedLoops, then
NestedLoops will return an iterator to you (without having performed
any iterations yet).

The iterator is a code reference.  Each time you call it, it returns the
next list of selected values.  Any arguments you pass in are ignored (at
least in this release).

=head3 Examples

=head4 Finding non-repeating sequences of digits.

One way would be to loop over all digit combinations but only selecting
ones without repeats:

    use Algorithm::Loops qw/ NestedLoops /;
    $|= 1;
    my $len= 3;
    my $verbose= 1;
    my $count= NestedLoops(
        [   ( [0..9] ) x $len  ],
        {   OnlyWhen => sub {
                    $len == @_
                &&  join('',@_) !~ /(.).*?\1/;
            #or &&  @_ == keys %{{@_,reverse@_}};
            }
        },
        sub {
            print "@_\n"   if  $verbose;
            return 1;
        },
    );
    print "$count non-repeating $len-digit sequences.\n";

    0 1 2
    0 1 3
    0 1 4
    0 1 5
    0 1 6
    0 1 7
    0 1 8
    0 1 9
    0 2 1
    ...
    9 8 5
    9 8 6
    9 8 7
    720 non-repeating 3-digit sequences.

But it would be nice to not waste time looping over, for example
(2,1,2,0,0) through (2,1,2,9,9).  That is, don't even pick 2 as the
third value if we already picked 2 as the first.

A clever way to do that is to only iterate over lists where the digits
I<increase> from left to right.  That will give us all I<sets> of
non-repeating digits and then we find all permutations of each:

    use Algorithm::Loops qw/ NestedLoops NextPermute /;
    $|= 1;
    my $len= 3;
    my $verbose= 1;
    my $iter= NestedLoops(
        [   [0..9],