Question: Dihedral symmetry: Perl vs Maple

Greetings to all. I am writing to present a Maple computation that is somewhat of a programming challenge. A recent Post at Math.Stackexchange.Com asked to compute the number of inequivalent colorings of the vertices and edges of a regular hexagon with two colors available for the vertices and three colors for the edges (vertex colors different from edge colors) under the simultaneous action of the dihedral group D6 on the vertices and edges. This is a standard application of Burnside's Lemma and can be computed very straightforwardly using a negligible amount of computing resources. Important: this is the accepted method, it is documented at the MSE link and it works quite well. The answer is that there are 4183 unique configurations.

My purpose in this message is to propose the following task: write a program in your favorite programming language to verify this number by enumerating all possible configurations, computing the orbits of each, and tracking the orbits to eventually arrive at, we hope, the answer, 4183 as stated. This being MaplePrimes the programming language in question is Maple, of course. I implemented the enumeration method and it can be found in the attachments to this message. The algorithm takes about two minutes on the machine that I used and peak memory allocation is about 70 MB. This made for a frustrating debug cycle as it needed a two minute wait to see the result of the changes made to the source code. I therefore decided to use Perl instead of Maple. Imagine my surprise when the very same algorithm (consult attachment) implemented in Perl had a running time on the same machine of about three seconds, used a hash table of about 1.6MB and had resident memory footprint of 6MB. (In fact the hash table can be reduced to half size by simplifying the keys which makes them a bit more difficult to read during debugging.) Let me state it like this: Perl vs. Maple resulted in a speed gain of a factor of forty and a memory savings of 90 percent.

Now how to profit from this experience. A question naturally appears at this point: can we optimize the Maple code so as to bring it into the range of the parameters of the Perl? Here we permit all sorts of optimizations that may occur to the Maple coder other than using Burnside where the motivation is that for many of us including myself there always remain additional Maple programming techniques to learn and acquire. I hope this makes for an enjoyable exercise and I am looking forward to seeing a Maple implementation that can compete with the Perl. This is not code golf but conciseness is a plus.



Happy computing!

Best regards, Marko Riedel

PS: I suspect working with hash tables rather than sets may be a start.

Please Wait...