2009/10/26 Michael Alipio <daem0n...@yahoo.com>:
> Then as suggested (see far below), a recursive function will do what I want..
> After some googling I found this:
>
>
> permutate(0,2);
>
> sub permutate($$){
>
> my ($cur,$max) = @_;
>
> if ($cur>=$max){
> print "$result\n";
> return;
> }
>
> for(@word){
> substr($result,$cur,1)=$_;
> perm($cur+1,$max);
> }
> }
>
>
> Can anyone tell me how the code above works?
Yes, not very well:
Undefined subroutine &main::perm called at foo.pl line 14.
ie you defined 'sub permutate' but you called 'perm()'. Please,
please, post *working* code if you want us to help you. I know what's
wrong and I can fix it myself, but you do yourself no favours by
making those who would help you work harder.
> My original program must deal with arbitrary length and generate all the
> possible combinations (even repeating) of a particular set. What could take
> me gazillions of for loops for that, somebody just came up with less than ten
> lines.
> I can just copy and paste the code I found above but I want to learn how it
> works. How could someone write this code so easily but when I tried even
> writing just a pseudocode for it, my head almost exploded.
>
> I want to be a good programmer, but at this rate, I don't think I can be one
> if I will just keep copying and pasting someone else's code or downloading
> modules from CPAN.
>
> Can anyone teach me how my own code (the one with gazillion for loops), can
> be converted into a pseudocode then eventually into a working sub procedure?
The code you found will teach you bad habits. Among other things:
* it uses the package variable $result to communicate between
recursive calls, rather than (in my version posted to the list a few
days ago) in an extra argument. This is a Bad Thing.
* it uses prototypes. Don't use prototypes; long story
http://xrl.us/bffo9k ; short story: prototypes are not like C
prototypes. They don't give you type safety. They don't force you to
use a scalar where it expects a scalar argument - you can still
provide an array or hash. And when you do, it will give you confusing,
hard-to-track-down bugs.
I would recommend you look instead at the code I posted to the list,
and I'll be happy to explain it to you.
As for how to "think in recursion", I find the best way to think is this way:
* How would I do it for a trivial case?
* Given I can do it for a case of size N-1, how would I do it for a
case of size N?
* How do I express this in perl?
As an example, the factorial function, the three steps become:
* How do I calculate 0!?
Answer: it is 1 by definition.
* Given that I can calculate (N-1)!, how do I calculate N! ?
Answer: I can calculate it thus: N * (N-1)!
* How do I express this in perl?
sub fact {
my ($n) = @_;
die "Can't calculate factorial of a negative or fractional number" if $n<0;
if ($n == 0) { # Base case
return 1;
}
# Solve fact($n) given we can already do fact($n-1)
return $n * fact ($n-1);
}
If you know your maths, this process is very similar to "proof by induction".
Philip
--
To unsubscribe, e-mail: beginners-unsubscr...@perl.org
For additional commands, e-mail: beginners-h...@perl.org
http://learn.perl.org/
