[sage-combinat-devel] Re: [Paul.Zimmermann-/[e-mail]: Re: SAGE Days 10.]

[Martin Rubey]

I could say a few things about how to work with the new partition
refinement code, if there is interest.

I'd like to see the slides, if possible.

Sure! And maybe a short demo as well. Here is a typical example of interest
to me and a student of mine. Fix a permutation group, let's say a subgroup of
S_10, and let it act on lists of length 10. Then generate all lists with 3
a', 2 b' and 5 c', up to isomorphisms.

So, actually you want (in Kerber's notation) elements of

G\\Y^X_{2,3,5}

(say: functions from X to Y with signature {2, 3, 5}), where

X = {0 1 2 3 4 5 6 7 8 9}

Y = {a b c}

and G is your permutation Group, acting on X.

In Kerber's book there is quite detailed description on how to go about
*exactly* this, but so far I have not really understood the connection to
Brendan Mc Kay's. Actually, Brendan Mc Kay himself writes in Isomorph-Free
Exhaustive Generation:

Most methods proposed for such problems can be classified into three types,
though the boundary between them is far from clear.

As I wrote before

http://groups.google.com/group/sage-combinat-devel/msg/849498b9479a7a70?hl=en

if we are able to solve this problem for a few species (most important being
k-subsets and set partitions), we can deal with many many objects, because the
Species constructors Times, Plus, Compose, FunctorialCompose can be described
just using these to species. I hurry to add that I have no idea at all how to
do set partitions under an arbitrary group action.

(And, for clarity, I should add that Nicolas' example is just a tiny bit more
general than subsets, but still within the scope of Kerber's methods. It just
happens that for Times I only need Subsets, not functions from X to {a,b,c}...)

Finally another datapoint:

For many examples, what Nicolas needs is already possible in the species code
of Ralf and myself. More precisely, we can generate the isotypes under the
group action of an arbitrary Young Subgroup (i.e., 2 a's, 3 b's, 5 c's) for
certain basic species (Set Partitions, k-Subsets, etc.) and *all* species you
can obtain from that using Times, Plus, Compose. Eg, binary forests with 2
labels "a", 3 labels "b" and 5 labels "c" should be roughly

macro {
CS == CombinatorialSpecies;
X == SingletonSpecies;
}
B(L: LabelType): CS L == Plus(X, Times(B,B))(L) add;
F(L: LabelType): CS L == Compose(SetSpecies, B)(L) add;

isomorphismTypes([a,a,b,b,b,c,c,c,c,c])$F(Symbol);


(but I didn't check. The compose part is the most tricky, obviously.)

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=/

[Martin Rubey]

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=/

[Nicolas M. Thiery]

Post by Martin Rubey
since I was asked to, I'll try to clarify my ideas to marry finite group
actions with species.

Thanks, that definitely helps!

Post by Martin Rubey
.. two basic species ..........................................................
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.

Do you mean ordered or unordered set partitions? That is do you
distinguish between the two following set partitions of {1,2,3}?

[{1,2} {3}] and [{3}, {1,2}]

Cheers,
Nicolas

[Martin Rubey]

Post by Nicolas M. Thiery

Post by Martin Rubey
since I was asked to, I'll try to clarify my ideas to marry finite group
actions with species.

Thanks, that definitely helps!

Post by Martin Rubey
.. two basic species ..........................................................
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.

Do you mean ordered or unordered set partitions? That is do you
distinguish between the two following set partitions of {1,2,3}?
[{1,2} {3}] and [{3}, {1,2}]

No, unordered. The species of set partition can be thought of
Set o NonEmptySet.

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=/