Skip to main content

Learning Perl5i #3

I've long admired the way functional languages specify multiple implementations of a routine for different sets of argument values, to detect terminal conditions. Converting a Perl6 solution  of a combinatorics task to Perl5i, I realized the plain Perl solution isn't necessarily all that bad, either.

The problem is to list the different ways you can select M elements from a set of N. Select 2 elements from a set of 4 would lead to the values ( 1, 2 ); ( 1, 3 ); ( 1, 4 ); ( 2, 3 ); ( 2, 4 ); ( 3, 4 ). Oh yeah, they want the characters in each combination in sorted order, and  the list of combinations sorted, too.

So it all consists of a single routine which gets invoked as combine(3, ['a'..'e']).

Ignore the first couple of lines, for a moment. If the first character of the set exists in a combination, it must be in the first position, since the characters are in sorted order. That means the remainder of the combination must be one character shorter, made of the remaining characters. So that part calls for a recursive solution:

* pull off the first character from the alphabet;
* recursively determine combinations of length -1 from the remainder of the set;
* reassemble be prefixing the first character onto each solution.

The other possibility is that the first character is not in the solution. That calls for recursively invoking the routine with the original length, but a smaller alphabet. If we do that often enough, we reach a situation where the alphabet is empty. This situation is handled by the first line we skipped over. In fact, we could optimize and abort if the size of the alphabet is smaller than the length of string we are requesting.

The more normal end case is when we are asking for a single character, the last in the sequence. In this situation, each character in the set is a candidate, so we return each character as an element in an anonymous array. Returning to the calling level, we then prefix the previous head of the alphabet onto the sequence using unshift. When we reach the top level, we have a list of arrays, each array being one combination.

While I was satisfied with the solution, I was unhappy with hard-coding the invocation. If I'm trying to demonstrate good coding, I should allow the program to be invoked with command-line arguments, to vary the way it is used.

So I added my favourite command-line options module, Getopt::Long, and modified the main section to fetch and use options:

my $options = parse_options();
say @$_ for combine( $options->{length}, 
                     @{$options->{alphabet}} );

The routine to read options looks like this:

func parse_options() {
    my %options = ( length => 3,
   set => 5,
    GetOptions( \%options, 'length=s', 'set=s' )
or die( 'some usage message';

    $options{alphabet} = 
        [ ('a'..'z')[0..$options{set}-1] ];
    return \%options;

Getopt::Long has a  rich set of options to support single character or long argument names, to allow flags, options with string or numeric values, hashes and even multiple values, as well as supporting multiple names and abbreviations. You can specify a parameter, and then specify a reference to a scalar in which to store the value, but I prefer to pass a reference to a hash as the first argument, which gets all the values.

By setting some values in the hash, you can specify default values.

In this case I allow two arguments, the length of the strings, M in combinatorics talk, and the size of the alphabet, N in combinatorics talk. I then create an alphabet of set N by taking an appropriately-sized subset of the sequence a to z.

But if GetOptions fails because the argument list is totally unusable, you need to report an error. And it should probably provide a usage message, describing how to invoke the program. My favourite solution is Pod::Usage, which makes it easy to display the POD contained in the file ... but that means documenting the program with POD.

So the question is, is this getting silly? Or is it an appropriate example to present to people wanting to learn modern Perl?

use perl5i::2;
use Getopt::Long;
use Pod::Usage;

# ----------------------------------------
# Generate combinations of length $len consisting
of characters from the sorted set @chars, using 
each character once in a combination,with sorted
# strings in sorted order.
# We will use a recursive solution:
# * If we run out of eligable characters, we've
#   gone too far, and won't find a solution along
#   this path.
# * If we are looking for a single character, each 
#   character in @set is eligible, so return each
#   as the single element of an array.
# * We have not yet reached the last character, so
#   there are two possibilities:
#   1) push the first element onto the front of an 
#      N-1 length combination from the remainder of
#      the set.
#   2) skip the current element, and generate an  
#      N-length combination from the remainder
func combine($len, @chars) {
  return unless @chars;
  return map { [ $_ ] } @chars if $len == 1;

  my ($head) = shift @chars;
  my @result = combine( $len-1, @chars );
  for my $subarray ( @result ) {
    $subarray->unshift( $head );
  return ( @result, combine( $len, @chars ) );

func parse_options() {
    my %options = ( length => 3,
   set => 5,
    GetOptions( \%options, 'length=s', 'set=s',
                'man', 'help' )
or pod2usage(2);
    pod2usage(1)  if $options{help};
    pod2usage(-verbose => 2)  if $options{man};

    $options{alphabet} =
        [ ('a'..'z')[0..$options{set}-1] ];
    return \%options;

my $options = parse_options();
say @$_
    for combine( $options->{length},
                 @{$options->{alphabet}} );


=head1 NAME

combinations.pli - determine possible combinations of M elements from a set of N

=head1 VERSION

This documentation applies to combinations.pli version 0.0.1


    combinations.pli [--length M] [--set N] \
                     [-man] [-help]

=head1 OPTIONS

=over 4

=item length M

Create strings of this length

=item set N

Use an alphabet of this many characters

=item help

Display a brief summary of information about the program.

=item man

Display the full documentation.



Generate combinations of length C<length> consisting of characters from the sorted set C<alphabet>, using each character once in a combination, with sorted strings in sorted order.


Post a Comment

Popular posts from this blog

Creating Perl5 Objects with Moxie

Having in the previous article prepared data types for car suits and card ranks, I can now combine them to provide a playing card class, using Stevan Little's Moxie module (version 0.04, so definitely early days.) The goal is to provide an object-oriented paradigm to the Perl 5 programming language which is more sophisticated, more powerful and less verbose than manually bless()-ing hashes. To achieve that goal it needs to be faster and light-weight compared to Moose. Currently, and and are add-on modules, but eventually, when they are more complete, when the wrinkles have been ironed out, and when they have gained acceptance and a community of users, they might be merged into the Perl core.

One significant feature of Moxie is that it reduces boilerplate code. You don't have to specify warnigns or strict. As well, the features or the perl you are using are enabled, among them say, state, signatures, and post_deref.
A Simple Moxie Class package Card { …

Perl5, Moxie and Enumurated Data Types

Moxie - a new object system for Perl5 Stevan Little created the Moose multiverse to upgrade the Perl 5 programming language's object-oriented system more in line with the wonderfull world of Perl 6. Unfortunately, it's grown into a bloated giant, which has inspired light-weight alternatives Moos, Moo, Mo, and others. Now he's trying to create a modern, efficient OO system that can become built into the language.

I've seen a few of his presentations at YAPC (Yet Another Perl Conference, now known as TPC, The Perl Conference), among them ‎p5 mop final final v5 this is the last one i promise tar gz<. So I was delighted to recently see an announcement of the module Moxie, and decided to try implementing a card game.

While the package provides some POD documentation about the main module, Moxie, it doesn't actually explain the enum package, Moxie::Enum. But delving into the tests directory reveals its secrets.
Creating an Enum package Ranks { use Moxie::Enum; …

BASH Matrix Multiplication

tl;dr Bash is not the language for math-intensive operations.

REPS=$1; FILE_1=$2; FILE_2=$3 OUTFILENAME=$4; readonly COLS=`head -1 $FILE_1 | wc -w`; readonly ROWS=`cat $FILE_1 | wc -l`; # echo "rows is $ROWS; cols is $COLS" if [[ $ROWS != $COLS ]]; then echo "Expecting square matrices, " \ "but rows = $ROWS, cols = $COLS\n"; exit 1; fi # -------------------------------------------------- # SUBROUTINES # function outputMatrix() { local matrixname=$1; local matrix; local elem; echo "matrix is '$matrixname'."; eval matrix=\( \${${matrixname}[@]} \); local i=0; for elem in "${matrix[@]}"; do echo -n "$elem "; if (( ++i == $COLS )); then echo ''; i=0; fi done } function multiply() { declare -a product; local M=$1 N=$2; local i j k idx1 idx2 idx3; for ((i=0; i < $ROWS; i++ )); do for ((j=0; j<$COLS; j++)); do …