Michael Alipio <daem0n...@yahoo.com> wrote:
> I knew I needed a recursive function, I just didn't know how to start.
That is usually the easy part - you start out by solving the problem for a base
case, and then you embellish.
With regard to your problem of generating all combinations of a set of
elements, the base case would be to just enumerate those elements.
For a longer result set with n elements (n being > 1), you'd then combine the
result for n-1 elements with the one element result set.
> What confused me more is that the code I found is a lot different from
> what I was initially thinking. He used the builtin function substr in the
> code in a way that I couldn't figure how it worked.
If in doubt, it pays off to RTFM ;-)
So you do "perldoc -f substr" and it'll tell you:
"You can use the substr() function as an lvalue, in which case EXPR must
itself be an lvalue."
It helps to know that lvalue is short for "left-hand value" and it basically
means that it behaves like a variable on the left hand side of the assignment
operator - it can be assigned a value.
The example from the man page helps to clarify this behavior:
my $name = 'fred';
substr($name, 4) = 'dy'; # $name is now 'freddy'
> What's the use of double ($$) after sub perm?? Does it have anything to
> do with process IDs (perldoc perlvar says so)?
Nope, these are prototypes for the function call (see perldoc perlsub, section
Prototype). Basically these two $$ signs make the function request two
arguments, which will be coerced to scalar values. This is of course only half
the truth, but I'll leave the nasty details and consequences to more erudite
folks on this list to explain ;-)
> This line is also confusing:
> substr($result,$cur,1)= $_;
>
> Substr returns a list, right? The first parameter is the expression, 2nd
> is the offset, and last is the length.
> The above line is too cryptic for me. What confused me more is that the
> return value of substr was assigned the $_.
Actually, substr() as an lvalue designates a part of the string $result that
will be assigned to, but please see above.
BTW, taking the recursive approach outlined above and using Iterators, my first
draft for a combination generator looks like this:
#!/usr/bin/perl -w
use strict;
#
# Iterator that generates all combinations of length $n of a set of elements.
#
sub gen_combo_iterator {
my( $n, @elements ) = @_;
# base case: iterator for all one element combinations
# This will just enumerate all elements of the set
if( $n == 1 ){
# this is a so-called closure - we return an anonymous subroutine that
# can still access the variables in its outer scope even though they
# are no longer visible for the rest of the program.
# subsequent calls to the anonymous function will manipulate a copy
# of the variable @elements that was created when the function was
# created by calling the outer subroutine.
return sub {
return shift @elements;
};
} elsif( $n > 1 ){
# recursion: all combinations of n elements are the product
# of all (n-1) element combinations x all 1 element combinations.
# this call with fall through until it reaches $n = 1
my $sub_combo_iterator = gen_combo_iterator( $n -1 => @elements );
# the second iterator has just one element
my $combo_iterator = gen_combo_iterator( 1 => @elements );
# we pick the first element
my $element = $combo_iterator->();
return sub {
if( my $sub_combo = $sub_combo_iterator->() ){
# if the iterator over all combinations of length n-1 still
# returns a value, combine it with my current item.
return $element . $sub_combo;
} else {
# try and pick a new element from the 1 element iterator
if( $element = $combo_iterator->() ){
# if there's a new element, reset the n-1 element iterator
$sub_combo_iterator = gen_combo_iterator( $n -1 => @elements );
# get a fresh element from the n-1 element iterator
$sub_combo = $sub_combo_iterator->();
# combine with the current element and return like above
return $element . $sub_combo;
} else {
# nothing more to return, we are finished.
return undef;
}
}
};
} else {
die "Assertion: $n must be a positive inter greater or equal 1";
}
}
#
# generate an iterator that will return all combinations of a given set
# with $min up to $max elements.
#
sub gen_all_combinations_iterator {
my( $min, $max, @elements ) = @_;
if( $min < $max ){
my $iterator = gen_combo_iterator( $min => @elements );
return sub {
if( my $result = $iterator->() ){
return $result;
} else {
$min++;
if( $min <= $max ){
$iterator = gen_combo_iterator( $min => @elements );
return $iterator->();
} else {
return undef;
}
}
}
} else {
die "Assertion: parameter $min must be smaller than parameter $max";
}
}
my $combo_iterator = gen_all_combinations_iterator( 1, 4 => qw/a b c d/ );
while( my $combo = $combo_iterator->() ){
print "$combo\n";
}
__END___
Keep in mind that the "=>" is really just a fancy way for writing a comma ;-)
Iterators are a concept pioneered by Lisp - the idea is that you deconstruct a
loop into successive function calls that keep their state between calls. That
way you don't have to generate all of the combinations at once beforehand and
then process them one by one, but you can start stepping through them right
away.
HTH,
Thomas
--
To unsubscribe, e-mail: beginners-unsubscr...@perl.org
For additional commands, e-mail: beginners-h...@perl.org
http://learn.perl.org/
