Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

robin (1821)

  (email not shown publicly)

Journal of robin (1821)

Wednesday August 22, 2001
07:33 AM

Permute! Permute! Custom ops?

[ #689 ]

I've been working on various things recently, mostly not very Perl-related. I found an answer to the permutations problem mentioned below. It's in a twenty-year-old paper written by a Cameroonian mathematician, published in a Canadian journal, which I found in the British Library. On the second page of the paper is exactly the same diagram that I'd been using.

One thing I've realised is that good permutation algorithms are not at all well-known. The algorithm in perlfaq4 is devastatingly slow, and the Cookbook entry is only a slight improvement. Algorithm::Permute is somewhat better (and written in C), but there's plenty of room for improvement.

The only way to list permutations really fast is to permute the array in-place, rather than copying the elements each time. Good permutation algorithms are fast enough that the overhead of copying the elements completely swamps the time taken to calculate the permutation. In complexity terms, copying the elements means that your algorithm will never be faster than O(n) to get the next permutation. We can get that down to O(1). And we still only need O(n) space.

So I'm thinking of writing Algorithm::Permute::InPlace. We should be able to make it scream. But if we write it in C, the overhead of calling the XSUB will still be quite heavy. So I'm toying with the idea of building an interface that will allow C routines to be called directly from the optree by the red-hot op dispatcher. I think that's a lot easier than it sounds. It would be nice to integrate it with Inline too. I hope to have a working proof of concept soon.