vivin has asked for the wisdom of the Perl Monks concerning the following question:

... you know, when your mind is like, in a bottle? Anyway, I was trying to do some permutations, and I wanted a recursive solution. I found a snippet of code that does it. However, I don't like putting code into my program without understanding what it does. This code gives me memories of my lisp class in college: 

#!/usr/bin/perl

print "permute:\n";
print "[", join(", ", @$_), "]\n" for permute([1,2,3], [4,5,6], [7,8,9
+]);

sub permute 
{
    my $last = pop @_;

    unless(@_) 
    {
           return map([$_], @$last);
    }

    return map { 
                 my $left = $_; 
                 map([@$left, $_], @$last)
               } 
               permute(@_);
}

[download]
Here's what I can figure out so far. The function goes into recursion until @_ is empty, at which point it returns [[1],[2],[3]] (or is it ([1],[2],[3])??) to the previous level of recursion. At that level, I know that $last is a reference to an array that contains [4,5,6]. From there, it gets sort of confusing (inside the map). This is mainly due to my lack of experience with map. I know what it does in principle, but applying it recursively and with $_, is giving me head-aches! Any help is appreciated. Thanks!

Replies are listed 'Best First'.
Re: This recursion is so "mind-bottling"
by ysth (Canon) on Apr 24, 2007 at 22:56 UTC
    at which point it returns [[1],[2],[3]] to the previous level of recursion.
    Important distinction: it returns ([1],[2],[3]), a list of three arrayref, not an arrayref to an array of three arrayrefs.

    So the outer map body is executed three times, first with $_ aliased to [1], then to [2], then to [3]. The inner map is run over (4,5,6) each of the three times, and returns, respectively, ([1, 4], [1, 5], [1, 6]), then ([2, 4], [2, 5], [2, 6]), then ([3, 4], [3, 5], [3, 6]), so the next-to-last recursive call returns ([1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6]).

    Hope this gets you further on.

[reply]
[d/l]
[select]
      Thanks a bunch, ysth, that made a whole lot clearer!
[reply]
OT Re: This recursion is so "mind-bottling"
by andye (Curate) on Apr 25, 2007 at 07:45 UTC
    ysth has already dealt with the meat of this, but I just wanted to mention that (unless you were joking) "mind-bottling" is an eggcorn for mind-boggling.

    Best wishes, andye

    PS I'm not trying to be the 'idiom police' here, just interested in how these things change over time and around the world. More on 'eggcorns' here and here.

[reply]
      Thanks for the links andye! I knew about these things but never knew they had a name.
[reply]
      Hehe, yeah I was joking. I just saw "Blades of Glory" and I liked to phrase. It also bothers me when people say "supposably" :)
[reply]

Back to Seekers of Perl Wisdom