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/