## Home Made Perl-based Permutor
Recently, I set about trying to write a simple, back-of-the-envelope
permutations generator which I needed for one of my personal projects.
I didn't want or need anything fancy as I was looking to avoid all the overhead
of loading external libraries and the related issues which come with that.
Furthermore, for the scope of my project, it was extremely likely that required
permutations would be of a limited nature (as in, not really taxing on modern
computing resources in anyway).
From a programming perspective (and I suspect that most if not all permutation
generators do this) I anticipated that this would involve some sort of
self-recursion (which, of course, it did).
### Review
To be sure, one has to be careful of poking around in recursive algorithms,
especially when generating permutations. Recall that permutations are
combinations of elements in which the **order** of the terms matters.
In other words, they differ from mere *combinations* in that combinations
ignore order (they pertain to groups) whereas permutations are lists.
For instance, a combination of:
```
123
```
is simply that. With all 1-2-3 in there, you've got the 1-2-3 grouping.
Permutations of 1-2-3, on the other hand, will give you:
```
123
132
213
231
312
321
```
In this case, there are 6 times as many permutations as there is a combination.
A very important consequence of this is that permutations follow a factorial
function of the number of terms:
```
Fear the formula: n!
[ Thus: 3! = 3 * 2 * 1 = 6 ]
```
At first glance one might think "Oh, that's fine" and sure, we can all do this
in our heads if we supply a few terms. You might even say to yourself - that's
easy, here's what I get:
```
1 term: 1 permutations
2 terms: 2 ..
3 terms: 6 ..
4 terms: 24 ..
5 terms: 120 ..
```
But notice the sudden take-off after hitting only 4-5 terms? Here's what
happens if we allow ourselves to go to beyond just a few:
```
6 terms: 720 permutations
7 terms: 5040 permutations
```
By the time we get to only 7 terms, we've already hit several thousand possible
permutations!
### The advantages of dedicated modules
That's why there are many heavy-duty [modules](http://search.cpan.org/search?query=Permutation&mode=all) to handle the generation
of permutations, all purpose-built by developers highly qualified for the task.
In the Perl world, there are two particular utilities which popular permutation
modules make use of and which are germane to the exercise at hand:
```
1). Iterators
2). Tail-call optimization
```
An iterator is a Perl object which generates the next value in a sequence.
This might not sound very useful at first but it does this by replicating
the sequence of our gigantic list (of, say, permutations) and returning the
next value that would appear in it without first generating that list and
storing it in an array and then reading from it.
Iterators don't get around the method of generating permutations - you still
need to write the permutor core function to interface with the iterator
returning the subsequent value. Nevertheless, depending on the size of the
list generated, use of iterators over conventional methods can be highly
advantageous when considered from a resource consumption perspective.
Tail-call optimization, in the context of recursion, is a programming method
which avoids the incremental allocation of new stack frames in memory with each
call of a function. During execution, arguments in the stack frame can be
updated/replaced by the last value returned from the called function, avoiding
the need to nest each call into its own memory space, thus also saving on
memory resources (and avoiding potential blow-ups). You can read more about
tail call optimization [here](https://en.wikipedia.org/wiki/Tail_call).
Unlike some other languages, tail-call optimization was never a native feature
of Perl and purpose-built modules mentioned above must emulate this behavior
programmatically. As a result, Perl comes with a 'deep recursion' warning
which is an error that is raised by Perl if it detects a function has called
itself too many times.
That limit was likely set some time ago when resources were much more limited
than they are today (it appears to be a hard coded number of around 100).
However, this warning can be turned off so that more recursions can be run.
Care should be taken when this is done, obviously, for the reasons mentioned
above.
Purpose-built permutation modules tend to integrate both of these important
features.
### My version
At any rate, while I was aware of these issues and the existence of such
modules and, *despite* the feeling of re-inventing the wheel, I was
determined to exercise the little gray cells to come up with a core
permutation function of my own.
As I thought through the process of permutations, I realized that it's
essentially all about swapping terms, a pair at a time, until you get to
the point of having no more terms to swap. Thus, I assembled a short
script to do what I needed.
You can [fork the script on GitHub](https://github.com/builderLabs/permutor), complete with ancillary routines.
The function permute is the core:
```
#==============================================================================
sub swapidx
{
my ( $idx_1, $idx_2 ) = @_;
($mapidx[$idx_1], $mapidx[$idx_2]) = ( $mapidx[$idx_2], $mapidx[$idx_1] );
}
#==============================================================================
#==============================================================================
sub permute
{
#-----------------------------------------------------------------
# Beginning from the end of our input array, swap pairs of
# elements until we have iterated through all indices
#-----------------------------------------------------------------
$cnt++;
#---first commit form as-is:
push @permutations, join("",@srcArray[@mapidx]);
my ( $idx1, $idx2 ) = ($arrLen-1,$arrLen);
while ( $idx1 >= 0 and $mapidx[$idx1] > $mapidx[$idx1+1] ){
$idx1--;
return(0) if ( $idx1 < 0 );
}
while ( $mapidx[$idx1] > $mapidx[$idx2] ) {
$idx2--;
}
swapidx($idx2, $idx1++);
$idx2 = $arrLen;
while ( $idx2 > $idx1 ) {
swapidx($idx2--,$idx1++)
}
die("Exiting after a lot of recursions ($cnt)...") if $cnt > $threshold;
#---loop such that all cnt-1 to end pairings have reversed
permute();
}
#==============================================================================
```
I wish I could say the whole exercise took me five minutes. It didn't.
Hindsight is 20/20, as they say, and, of course, I kicked myself for not
having arrived at the solution earlier than I did.
Nevertheless, persistence was an important takeaway in this exercise for me
for which I'm reminded of Hugh Laurie's inimitable line as Lieutenant George
from *Blackadder*: "We got there in the end, eh, Baldrick?"
