Samir Parikh

(Originally published on samirparikh.com.)

In one of my earlier posts describing how I solved the Perl Weekly Challenge tasks, I mentioned that I got a bit lazy and resorted to using a CPAN module to determine all of the combinations of elements to satisfy the conditions of the puzzle. One of the things that drew me to Perl in the first place is the almost 200,000 ready-to-go modules available in CPAN to help you solve almost any conceivable problem. Chances are, if you have a programming issue to solve, someone else already has. There's a reason the "C" in CPAN stands for "Comprehensive"! As someone who is trying to learn Perl, I think it's a valuable skill to know how to search the archive and leverage these modules. It's what allows you to extend Perl beyond it's standard capabilities. And truth be told, I know that a big part of solving combination and permutation problems often requires the use of recursive functions, something I can never get my head around no matter what programming language I'm using. But something has been nagging me over the past few days since I wrote that blog article to the point where the guilt about being too lazy and the void left about not really understanding recursion finally pushed me over the edge to tackle this one more time.

Recursion is the act of solving a complex problem by breaking it down into smaller and smaller subsets of the same problem. A classic example is using recursion to determine the next number in the Fibonacci sequence. Beginning with 0 and then 1, each successive number in the Fibonacci sequence is equal to the sum of the prior two numbers. Therefore, if F0 = 0 and F1 = 1, then the third number, represented by F2, is equal to F1 + F0. Therefore:

F2 = F1 + F0

F2 = 1 + 0

F2 = 1

Likewise, the fourth number in the sequence, F3, can be calculated as:

F3 = F2 + F1

F3 = (F1 + F0) + F1

F3 = 1 + 0 + 1

F3 = 2

Therefore, the first 10 numbers in the Fibonacci sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

You can generalize the sequence such that

Fn = Fn-1 + Fn-2

for n > 1 and using this information, we can create a recursive function in Perl (or any other language) as follows:

sub fibonacci {
    if ($_[0] == 0) {
        return 0;
    } elsif ($_[0] == 1) {
        return 1;
    } else {
        return &fibonacci($_[0] - 1) + &fibonacci($_[0] - 2);
    }
}

print &fibonacci(7), "\n"; # 13

The function is recursive because it calls itself. The reason this doesn't turn into an endless loop is that we first check whether a "base case", or terminating condition, is satisfied before we have the function call itself. In this situation, the base case is whenever n = 0 or n = 1. Recursion can be used to algorithmically solve other problems as well, such as calculating the factorial of a number or in solving the Towers of Hanoi puzzle. For my case though, I wanted to see if I could come up with a function to calculate all of the permutations of the elements of an array without using a Perl CPAN module.

There are many tutorials and articles on the internet that show you various implementations of a recursive function to derive permutations. And there are no shortage of Perl-specific implementations as well. For example, the Perl FAQ page contains an implementation as does the Perl Cookbook. For my implementation, however, I took inspiration from CPalli's article on a Python implementation of a recursive function to find permutations. I found his writeup to be more insightful and easier to understand than many of the other articles I came across. I encourage you to read it before continuing here as it will help explain the logic behind my Perl port of it. The key insight I took away from CPalli's post is that to find the n! (factorial) permutations of n elements in an array, you temporarily remove one element, find all the permutations of the remaining elements, and then add the element you originally removed back to the permutations you found. This gives you all possible permutations for your elements. The base case in this example is if you only have one element, in which case the only permutation is that element itself.

To illustrate this with the simple example of three elements (1, 2, 3), he has a neat visualization that demonstrates this recursive property:

                          1 2 P[3]  =  1 2 3
             1 P[2 3]  =
                          1 3 P[1]  =  1 3 2


                          2 1 P[3]  =  2 1 3    
P[1 2 3]  =  2 P[1 3]  = 
                          2 3 P[1]  =  2 3 1


                          3 1 P[2]  =  3 1 2
             3 P[1 2]  = 
                          3 2 P[1]  =  3 2 1

This can be generalized to:

                1 P[2 3 .. N]

                2 P[1 3 .. N]

P[1 2 .. N] =   ..

                ..

                N P[1 2 .. (N-1)]

which can form the basis of our recursive function. Again, CPalli does a nice job in his blog post detailing a recursive solution to this using Python. He walks through an example and shows how the permutations are derived step-by-step. Using his example, I came up with the following Perl implementation:

#!/usr/local/bin/perl

use warnings;
use strict;
use v5.10;

sub perm {
    my @out;
    my @in = @_;
    if (scalar(@in) == 1) {
        return @in;
    } else {
        for my $i (0 .. $#in) {
            foreach (&perm(@in[0 .. $i-1], @in[$i+1 .. $#in])) {
                push(@out, $in[$i].$_);
            }
        }
    }
    return @out;
}

say join(", ", &perm(1 .. 3)); # 123, 132, 213, 231, 312, 321

The key insight I referred to earlier is implemented in the push function, specifically this bit here:

$in[$i].$_

which adds back the element that was originally removed ($in[$i]) to the permutations of the remaining elements that were returned by the recursive call to the perm subroutine in the preceding line.

It works, but I'm not terribly happy about it. My main issue is that the subroutine returns an array of the permutations in a string format (e.g. 123, 132, 213, 231, 312, 321), like the Python implementation it was modeled on. I'd prefer if each permutation was returned as an array, something like:

[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

That way, you can more easily iterate through the results which is typically what you want to do with the permutations. If anyone has any suggestions on how to make that happen, perhaps with the use of references and arrays of arrays or something similar, please let me know! I've already started thinking about this!

Apologies for the unclear subscripts above when discussing the Fibonacci sequence. I'm not sure how to create subscripts using the Moveable Type flavor of Markdown.