Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

permutation understanding

by Parham (Friar)
on May 25, 2002 at 01:06 UTC ( [id://169231] : perlquestion . print w/replies, xml ) Need Help??

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

i'll start off by saying, the only reason i redid the coding was to try and understand what was going on. I took the permutation subroutine from the perl cookbook and redid it without the use of passing arrays (i'm passing simple variables now, constructing and destructing them into arrays). I can better see how the program works now:
#!/usr/bin/perl use strict; permute("1 2 3 4",""); sub permute { my $old = @_[0]; my $new = @_[1]; my @old = split(/ /,$old); my @new = split(/ /,$new); print "old = @old | new = @new\n"; #helpful in seeing what's going o +n unless (@old) { print "@new\n"; } else { my $i; foreach $i (0..$#old) { my @new1 = @new; my @old1 = @old; unshift(@new1,splice(@old1,$i,1)); my $new1 = join(' ',@new1); my $old1 = join(' ',@old1); permute($old1,$new1); } } }
Fellow monks, i require your assistance in understanding this permutation program. The commented line shows what the function is doing while making the permutations:
old = 1 2 3 4 | new = 
old = 2 3 4 | new = 1
old = 3 4 | new = 2 1
old = 4 | new = 3 2 1
old =  | new = 4 3 2 1
4 3 2 1
old = 3 | new = 4 2 1
old =  | new = 3 4 2 1
3 4 2 1
old = 2 4 | new = 3 1
old = 4 | new = 2 3 1
old =  | new = 4 2 3 1
4 2 3 1
... too long to continue
i understand everything up to the first loop, but after that i start losing how the "old" array picks up info from the "new" array (seems to be working backwards?). I'm not having a perl problem, but rather a theory problem with how perl actually makes this work. If someone could give me a short step-by-step guide to what perl does with the array, i'd be most grateful. Rather than using the subroutine blindly, i'd like to get a little bit of information on how it's able to work. All help appreciated, and thanks in advance.

Replies are listed 'Best First'.
(jeffa) Re: permutation understanding
by jeffa (Bishop) on May 25, 2002 at 09:02 UTC
    Ahh ... recursion!
    Ahh ... recursion
    Ahh ... recursio
    Ahh ... recursi

    Sounds like you need to focus on recursion right now instead of permutations. Forgive me for dodging the original question, but since the Cookbook really covers this better than i can, i hope my new problem will shed some favorable light. Contemplate this:

    use strict; eat('Ahh ... recursion!'); sub eat { my $food = shift; if ($food) { print "$food\n"; eat (substr($food,0,length($food)-1)); } else { # base case return; } }
    First, we call the function with a value. Inside this function we check to see if $food is true. Since $food is 'Ahh ... recursion!', it is indeed true, so we print it and call the function again with a new value - the orginal value minus the last character. This continues on and on and on and on until there are no characters left in the variable $food. When we have exhausted $food, the else 'kicks in' and we return - without this, we would be caught in an infinite loop. Well, not really. Because Perl returns (a false value in this example) by default, we don't have to worry about explicitly returning (for this example). You can safely remove the else and it's block, but if you remove the if, the program will loop infinitely.

    So, how does this work? Every time you call a subroutine, something has to preserve the arguments you have passed to it. This is implemented internally via a stack. A stack is simply a list that is accessed first-in first-out oops, LAST-in first out (thanks Albannach!), just like a stack of plates at the all-you-can-eat bar. Each call to the function eat() places the argument list on the stack - when the base case (i.e. $food is false) is finally reached, the stack is unwound. Consider this now, the same example using an explicit stack:

    use strict; my @stack = ('Ahh ... recursion!'); eat() while @stack; sub eat { my $food = pop @stack; if ($food) { print "$food\n"; push @stack, substr($food,0,length($food)-1); } }
    Very similar, but not the same. First, we define the stack with one element: 'Ahh ... recursion!'. Next we call the function eat in a while loop: we eat() until @stack is false (and a false array is one that has no elements).

    Inside the function eat(), we first pop the first element out of @stack and store this value in $food. Next we check to see if $food is true (AKA, is not empty). If it is true, we print it, remove the last character, and push back on @stack. This continues until we have removed all the characters - effectively 'eating' the string up. When the string $food is only one character long, we push the result of the final substr (an empty string) onto @stack. Now the while loop fails, and the program ends.

    I really hope this helps, because personally, recursion is tough. As a final note, try to understand this program - the Fibonacci sequence (hint - google Fibonacci sequence to learn more):

    use strict; my $numb = shift || 20; print fib($numb), "\n"; sub fib { my $n = shift; return 1 if $n < 2; return fib($n - 2) + fib($n - 1); }
    Anony is correct - a better test would have been:
    if (length $food) ... # instead of if ($food) ...


    (the triplet paradiddle with high-hat)
      if ($food) { print "$food\n"; eat (substr($food,0,length($food)-1)); }

      Yes recursion can be instructive, but be careful not to mismatch a conditional test with the logical intent of the test. Your test of true or false doesn't mesh with your logical intent of recursing based on the length of the string. Try eating the string "012345" and your recursion ends too early because a string can have a non-zero length and still be false.

        A simple fix:
        if (exists $food) { }
        Update: Oops, I jumped the gun on that one.

        mr greywolf
Re: permutation understanding
by Parham (Friar) on May 27, 2002 at 20:55 UTC
    i actually thought i'd do a followup on this post, cuz i got a little better understanding of how it works.

    Take the inputted number, now move the first number to the beginning of a new list. Take the old and new lists and permute those. Take the first number of the old list and take it to the new list. Permute the two lists. Take the first number of the old list and move it to the new list.

    Each time, check to see if the old list is completely empty, if it is, start moving backwards in foreach loops. Go back one foreach loop, move the second number to the new list, and permute those two lists. It's weird to explain, so i'd rather show you what i came up with hoping that this will help those who didn't understand how the permutation worked.

    The follwing two URL's show how the permutation works. The first link is a simple explanation of a list of three elements (x, y, and z) while the second takes a deeper look at a list with four elements (1, 2, 3, and 4)

    simple interpretation
    actual example using four elements

    i hope these help people who don't quite know how the function works :).