view release on metacpan or  search on metacpan

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

list context.  So we need to use C<scalar> or
something similar if we want to read only one
line at a time from C<IN> above. ]

Want to sort strings that contain mixtures of
letters and natural numbers (non-negative
integers) both alphabetically and numerically
at the same time?  This simple way to do a
"natural" sort is also one of the fastest.
Great for sorting version numbers, file names,
etc.:

    my @sorted= Filter {
        s#\d{2}(\d+)#\1#g
    } sort Filter {
        s#(\d+)# sprintf "%02d%s", length($1), $1 #g
    } @data;

[ Note that at least some versions of Perl have a bug that breaks C<sort>
if you write C<sub {> as part of building the list of items to be sorted
but you don't provide a comparison routine.  This bug means we can't
write the previous code as:

    my @sorted= Filter {
        s#\d{2}(\d+)#\1#g
    } sort Filter sub {
        s#(\d+)# sprintf "%02d%s", length($1), $1 #g
    }, @data;

because it will produce the following error:

    Undefined subroutine in sort

in some versions of Perl.  Some versions of Perl may even require you
to write it like this:

    my @sorted= Filter {
        s#\d{2}(\d+)#\1#g
    } sort &Filter( sub {
        s#(\d+)# sprintf "%02d%s", length($1), $1 #g
    }, @data );

Which is how I wrote it in ex/NaturalSort.plx. ]

Need to sort names?  Then you'll probably want to ignore letter case and
certain punctuation marks while still preserving both:

    my @compare= Filter {tr/A-Z'.,"()/a-z/d} @names;
    my @indices= sort {$compare[$a] cmp $compare[$b]} 0..$#names;
    @names= @names[@indices];

You can also roll your own simple HTML templating:

    print Filter {
        s/%(\w*)%/expand($1)/g
    }   $cgi->...,
        ...
        $cgi->...;

Note that it also also works correctly if you change how you output your
    HTML and accidentally switch from list to scalar context:

    my $html= '';
    ...
    $html .= Filter {
        s/%(\w*)%/expand($1)/g
    }   $cgi->...,
        ...
        $cgi->...;

=head3 Motivation

A reasonable use of map is:

    @copy= map {lc} @list;

which sets @copy to be a copy of @list but with all of the elements
converted to lower case.  But it is too easy to think that that could
also be done like this:

    @copy= map {tr/A-Z/a-z/} @list;  # Wrong

The reason why these aren't the same is similar to why we write:

    $str= lc $str;

not

    lc $str;  # Useless use of 'lc' in void context

and we write:

    $str =~ tr/A-Z/a-z/;

not

    $new= ( $old =~ tr/A-Z/a-z/ );  # Wrong

That is, many things (such as lc) return a modified copy of what they are
given, but a few things (such as tr///, s///, chop, and chomp) modify
what they are given I<in-place>.

This distinction is so common that we have several ways of switching
between the two forms.  For example:

        $two= $one + $other;
  # vs.
        $one += $other;

or

        $two= substr($one,0,4);
  # vs.
        substr($one,4)= '';

I've even heard talk of adding some syntax to Perl to allow you to make
things like C<lc> become reflexive, similar to how += is the reflexive
form of +.

But while many non-reflexive Perl operations have reflexive counterparts,
there are a few reflexive Perl operations that don't really have

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

So, if you start out with a sorted array, then you can use that as your
first permutation and then call NextPermute* to get the next permutation
to use, until NextPermute* returns a false value (at which point your
array has been returned to its original, sorted order).

So you would use NextPermute() like this:

    my @list= sort GetValuesSomehow();
    do {
        DoSomethingWithPermutation( @list );
    } while(  NextPermute( @list )  );

or, if your list only contains numbers, you could use NextPermuteNum()
like this:

    my @list= sort {$a<=>$b} GetNumbersSomehow();
    do {
        DoSomethingWithPermutation( @list );
    } while(  NextPermuteNum( @list )  );

=head3 Notes

The NextPermute* functions each have a prototype specifications of (\@).
This means that they demand that you pass them a single array which they
will receive a reference to.

If you instead have a reference to an array, you'll need to use C<@{ }>
when calling a NextPermute* routine:

    } while(  NextPermute( @{$av} )  );

(or use one of several other techniques which I will leave the
consideration of as an "exercise" for the more advanced readers
of this manual).

Note that this particular use of a function prototype is one that I am
not completely comfortable with.  I am tempted to remove the prototype
and force you to create the reference yourself before/when calling these
functions:

    } while(  NextPermute( \@list )  );   # Wrong

because

=over 4

=item

It makes it obvious to the reader of the code that a reference to the
array is what is being used by the routine.  This makes the reader more
likely to realize/suspect that the array is being modified in-place.

=item

Many/most uses of Perl function prototypes are more trouble than they are
worth.  This makes using even the less problematic cases often not a good
idea.

=back

However, I have decided to use a prototype here because:

=item

Several other functions from this module already use prototypes to good
advantage, enough advantage that I'd hate to lose it.

=item

Removing the prototype would require the addition of argument-checking
code that would get run each time a permutation is computed, somewhat
slowing down what is currently quite fast.

=item

The compile-time checking provided by the prototype can save develop time
over a run-time check by pointing out mistakes sooner.

=back

=head3 Features

There are several features to NextPermute* that can be advantages over
other methods of finding permutations.

=over 4

=item Iterators - No huge memory requirements

Some permutation generators return the full set of all permutations (as a
huge list of lists).  Your input list doesn't have to be very big at all
for the resulting set to be too large to fit in your available memory.

So the NextPermute* routines return each permutation, one at a time, so
you can process them all (eventually) without the need for lots of memory.

A programming object that gives you access to things one-at-a-time is
called an "iterator".

=item No context - Hardly any memory required

The NextPermute* routines require no extra memory in the way of context
or lists to keep track of while constructing the permutations.

Each call to a NextPermute* routine shuffles the items in the list
B<in-place>, never making copies of more than a couple of values at a
time (when it swaps them).

[ This also means you don't have to bother with creating an object to do
the iterating. ]

=item Handles duplicate values

Unlike most permutation generators you are likely to find in Perl, both
NextPermute* routines correctly deal with lists containing duplicate
values.

The following example:

    my @list= ( 3, 3, 3, 3 );
    do {