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.
