Derangements, bell permutations, involutions and more

The last few days I have been implementing mostly generic iterables algorithms to generate various combinatorial objects such as Bell permutations, involutions and derangements, cyclic permutations and up-and-down permutations. As I have mentioned before, this goes more into the exercises portion of TAOCP. This is why the algorithms implemented for these routines are not the most optimized versions but are good enough. Another point to note is that these areas are still an active topic of research and many new papers are available that show how to generate these kinds of specialized combinatorial objects in a more efficient manner.

One favorite example of mine is this paper by Vincent Vajnovszki in which he introduces the ECO operator

Although several efficient, loopless, constant amortized time algorithms exist, they are all fairly distinct in their approaches. The above paper seeks to unify such structures using the ECO operator as a common theme. Another theme the author has addressed is the generation of p-ary Dyck Gray codes. To implement this I will be leveraging the already existing gray code infrastructure. To what extent though, I am not too sure.

There has also been a lot chatter lately on a Graph theory module for Sympy. Before the Gsoc started I had already written some code that tried to interface networkx and pygraphviz with Sympy and this sort of served as a prototype of the project. Anyway, I did mention that I would be integrating networkx into Sympy for implementing spanning tree generation. There is also the fact that a lot of stuff in the previous modules that is implemented by Mathematica that is incomplete because there is no Graph module. The presence of a graphing module, whether native or imported, is almost axiomatic to any complete CAS. Thus integrating networkx will be my task for the following week.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: