Dear Robert, Mike, Ralf, since I was asked to, I'll try to clarify my ideas to marry finite group actions with species. Actually, I believe that most of what we would need is implemented in Symmetrica, and that species are mostly just another language to formulate problems in combinatorial generation.
-- skip this if you know species ---------------------------------------------- Why bother with species? One strong point of species is that it provides us with a very intuitive language to describe many combinatorial objects. For example, binary trees are just B = 1 + B*X*B read: a binary tree is either the empty tree or two trees attached to a vertex. In the equation above, 1, X and B are species, and + and * are operations on species. Thus we can build more interesting species from very simple ones, by using a few operations, the more important ones being: +, *, composition (AKA as plethystic substitution), pointing, functorial composition. In the traditional description of combinatorial species, one desire was to unify tools for labelled and unlabelled objects. This is achieved by having two "versions" of all the operations +, *, ... Really, what is happening is that one lets the symmetric group act on the labels of the object and generates the isomorphism types. ------------------------------------------------------------------------------- Why general isomorphism types? Now, it turned out that for implementing the unlabelled version of plethystic substitution, one actually needs the ability to generate isomorphism types of objects where a Young subgroup S_n1 x S_n2 x ... acts on the labels. This was done in aldor combinat (in the iso-experiment branch). Next, I wanted to implement the unlabelled version of functorial composition (to generate unlabelled graphs, for example), and it turned out that I need the ability to generate isomorphism types of objects under yet another family of group actions. Since we want both plethystic and functorial substitution, we actually need to be able to generate iosomorphism types of objects under an *arbitrary* group action. ------------------------------------------------------------------------------- What we need and how to do it? Basically, we need for every species a function (in Pseudo-Aldor notation, but it should be very similar in Sage) isomorphismTypes(U: Set, H: Subgroup of S_U) that returns representatives of the objects labelled with the elements in U under the group action given by H. I guess, that it's easiest to describe H as a list of generators, but that's not so important for now. (It will probably be important for speed, though) .. two basic species .......................................................... Now, there are not many Species that we need. Actually, to get started we only need implementations for the species of k-Subsets and the species of set partitions. The species of k-Subsets produces for every set U all subsets of U with k elements. I have no idea whether this is feasible with Roberts code, but it is available in symmetrica, see http://www.mathe2.uni-bayreuth.de/frib/html/symman/manual_37.html The species of set partitions is probably more complicated, it is already quite complicated when the group acting is a Young subgroup S_n1 x S_n2 x ... But maybe Robert's code could help here. Of course, there are other species for which we would like to have implementations, for example, the species of cycles. Curiously, cycles and necklaces (which are cycles under the action of a Young subgroup) can themselves be described as mappings Y^X under the action of the cyclic group (acting on X). I didn't check, but I guess that arbitrary actions on cycles fall in the same framework. .. and a few operations ....................................................... Given implementations for k-subsets and set partitions, it is straightforward to implement all the operations I mentioned before, the trickiest probably being plethystic composition. Actually, the algorithms for + and * stay exactly as they are. I guess that for plethystic composition one can reuse the one in aldor-combinat. --- speed --------------------------------------------------------------------- Very likely, using this very general framework imposes a speed penalty. But I believe that it's better to have something working, albeit slow, than to try to get something fast immediately. ------------------------------------------------------------------------------- I'm not sure whether this makes my idea clearer in comparison to http://groups.google.com/group/sage-combinat-devel/browse_thread/thread/a8bed1604cc6053a?hl=en But maybe it's now easier to pinpoint things that are unclear. If you could send me an example that shows how to call all_orbits_right(g,m,v) from symmetrica, maybe I could provide some code. Martin ------------------------------------------------------------------------- This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK & win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100&url=/ _______________________________________________ Aldor-combinat-devel mailing list Aldor-combinat-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/aldor-combinat-devel
