about blog projects contact

The Cogwheel Blog

Fork me on GitHub
## 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?"

-A. Ozan Akcin