view release on metacpan or  search on metacpan

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

In a list context, NestedLoops C<push>es the values returned by each call
to \&Code onto an array and then returns (copies of the values from) that
array.

In a scalar contetx, NestedLoops keeps a running total of the number of
values returned by each call to \&Code and then returns this total.  The
value is the same as if you had called NestedLoops in a list context and
counted the number of values returned (except for using less memory).

Note that \&Code is called in a list context no matter what context
NestedLoops was called in (in the current implementation).

In summary:

    NestedLoops( \@loops, \%opts, \&code );
    $count= NestedLoops( \@loops, \%opts, \&code );
    @results= NestedLoops( \@loops, \%opts, \&code );

=head4 \@Loops

Each element of @Loops can be

=over 4

=item an array refernce

which means the loop will iterate over the elements of that array,

=item a code refernce

to a subroutine that will return a reference to the array to loop over.

=back

You don't have to use a reference to a named array.  You can, of course,
construct a reference to an anonymous array using C<[...]>, as shown in
most of the examples.  You can also use any other type of expression that
rerurns an array reference.

=head4 \%Opts

If %Opts is passed in, then it should only zero or more of the following
keys.  How NestedLoops interprets the values associated with each key are
described below.

=over 4

=item OnlyWhen => $Boolean

=item OnlyWhen => \&Test

Value must either be a Boolean value or a reference to a subroutine that
will return a Boolean value.

Specifying a true value is the same as specifying a routine that always
returns a true value.  Specifying a false value gives you the default
behavior (as if you did not include the OnlyWhen key at all).

If it is a code reference, then it is called each time a new item is
selected by any of the loops.  The list of selected items is passed in.

The Boolean value returned says whether to use the list of selected
values.  That is, a true value causes either \&Code to be called (if
specified) or the list to be returned by the iterator (if \&Code was not
specified).

If this key does not exist (or is specified with a false value), then a
default subroutine is used, like:

    sub { return @_ == @Loops }

That is, only complete lists are used (by default).  So:

    my @list= NestedLoops(
        [  ( [ 1..3 ] ) x 3  ],
        {  OnlyWhen => 0  },
        sub { "@_" },
    );

is similar to:

    my @list= qw/ 111 112 113 121 122 123 131 132 133 211 212 ... /;

while

    my @list= NestedLoops(
        [  ( [ 1..3 ] ) x 3  ],
        {  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],
            ( sub { [$_+1..9] } ) x ($len-1),
        ],
    );
    my $count= 0;
    my @list;
    while(  @list= $iter->()  ) {
        do {
            ++$count;
            print "@list\n"   if  $verbose;
        } while( NextPermute(@list) );
    }
    print "$count non-repeating $len-digit sequences.\n";

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

A third way is to construct the list of values to loop over by excluding
values already selected:

    use Algorithm::Loops qw/ NestedLoops /;
    $|= 1;
    my $len= 3;
    my $verbose= 1;
    my $count= NestedLoops(
        [   [0..9],
            ( sub {
                my %used;
                @used{@_}= (1) x @_;
                return [ grep !$used{$_}, 0..9 ];
            } ) x ($len-1),
        ],
        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
    0 2 3
    ...
    9 7 8
    9 8 0
    9 8 1
    9 8 2
    9 8 3
    9 8 4
    9 8 5
    9 8 6
    9 8 7
    720 non-repeating 3-digit sequences.

Future releases of this module may add features to makes these last two
methods easier to write.

=cut


    use Algorithm::Loops qw( NestedLoops );
    my @choices= qw/ a b c f /;
    my $picks= 3;
    my %picked;
    print join $/, NestedLoops(
        [ ( \@choices ) x $picks ],
        {   OnlyWhen => sub {
                return -1   if  $picked{$_};
                $picked{$_}= 1;
                return  $picks == @_;
            },
            Post => sub {