Orbits of tuples and sets #14291

nathanncohen · 2013-03-17T11:24:28Z

A small patch to let us compute the orbits of sets and tuples by exposing it from GAP.

Apply :

CC: @dimpase

Component: group theory

Author: Nathann Cohen, Volker Braun

Reviewer: Volker Braun

Merged: sage-5.10.beta0

Issue created by migration from https://trac.sagemath.org/ticket/14291

nathanncohen · 2013-03-17T11:26:20Z

comment:1

There is a small problem with cached functions right now... -_-

Nathann

dimpase · 2013-03-17T12:44:17Z

comment:2

this looks weird:

def orbit(self, point, onsets = False, ontuples = False):

What about

def orbit(self, point, action = "onpoints"):

(or "OnPoints" ?) which is the default,
and then sort out the cases action = "onsets", etc. ?

nathanncohen · 2013-03-17T13:04:17Z

comment:3

Totally right...

Just updated it ! And the function only takes tuples as arguments now. I so hate it when design decisions have to be changed for technical issues -_-.

Nathann

nathanncohen · 2013-03-17T13:04:28Z

Attachment: trac_14291.patch.gz

dimpase · 2013-03-19T06:00:16Z

comment:4

There are more useful permutation group actions, see http://www.gap-system.org/Manuals/doc/ref/chap41.html

Namely, OnPairs, OnSetsSets, OnSetsDisjointSets, OnSetsTuples, OnTuplesSets, OnTuplesTuples all should work just fine.

One has to canonize the representative to start with, for some of them, see here. E.g.

Orbit(SymmetricGroup(5),Set([[2,4],[1,3]]),OnSetsSets);

is OK, but

Orbit(SymmetricGroup(5),[[2,4],[1,3]],OnSetsSets);

gives an error.

Less sure about OnIndeterminates.

There is also a support for user-defined actions, but this would mean either specifying a piece of GAP code, or providing a callback, which seems to be too crazy to implement.

nathanncohen · 2013-03-19T09:45:07Z

comment:5

Helloooooooo !!

There are more useful permutation group actions, see http://www.gap-system.org/Manuals/doc/ref/chap41.html

Yepyep, I saw them but I really only need OnTuples and OnSets myself, and as I do not really see how I could use the others I do not think that it would be wise to expose them myself. Soooo unless you want to write that additional patch yourslf, ... :-)

Nathann

dimpase · 2013-03-19T16:05:14Z

comment:7

Replying to @nathanncohen:

Helloooooooo !!

There are more useful permutation group actions, see http://www.gap-system.org/Manuals/doc/ref/chap41.html

Yepyep, I saw them but I really only need OnTuples and OnSets myself, and as I do not really see how I could use the others I do not think that it would be wise to expose them myself. Soooo unless you want to write that additional patch yourslf, ... :-)

OK, needs your review now :-P

nathanncohen · 2013-03-19T16:09:28Z

comment:8

OK, needs your review now :-P

Cool :-P

Well, for a start sage -coverage will not like the documentation of supported_actions at all. Why do you want to create a function just to list them ? Why don't you just include in the methods, or make it a variable in the module ? (anyway you still have to split cases in orbits in order to know what to return).

Would it be possible to add a link toward GAP's documentation where all those actions are defined ?

Nathann

dimpase · 2013-03-19T17:07:09Z

comment:9

Attachment: 14291_reviewer.patch.gz

Replying to @nathanncohen:

OK, needs your review now :-P

Cool :-P

Well, for a start sage -coverage will not like the documentation of supported_actions at all. Why do you want to create a function just to list them ? Why don't you just include in the methods, or make it a variable in the module ? (anyway you still have to split cases in orbits in order to know what to return).

made it a variable...

Would it be possible to add a link toward GAP's documentation where all those actions are defined ?

added...

nathanncohen · 2013-03-19T22:22:26Z

Attachment: trac_14291-rev2.patch.gz

nathanncohen · 2013-03-19T22:38:31Z

comment:10

Some small modifications to the documentation. Besides this :

What would you think of making supported_actions a variable of the module itself ? And what of making it a hidden variable ?
What would you think of sorting the input when it represents a set ?.. GAP's error message when it is fed with an unsorted list is not that clear :

Error, OnSets: <set> must be a set (not a list (plain,cyc,nsort,imm))

I will do that if you agree with it.

Nathann

dimpase · 2013-03-19T23:48:00Z

comment:11

Replying to @nathanncohen:

Some small modifications to the documentation. Besides this :

What would you think of making supported_actions a variable of the module itself ? And what of making it a hidden variable ?

The current setup allows it to be extended by the user. One can install via gap.eval() a GAP function, say, "OnBlah", and then use it. You can't do this with a module variable.

What would you think of sorting the input when it represents a set ?.. GAP's error message when it is fed with an unsorted list is not that clear :
Error, OnSets: <set> must be a set (not a list (plain,cyc,nsort,imm))
I will do that if you agree with it.

sure this can be done as you prefer. However, there is a more serious issue with self.action:

sage: G = PermutationGroup([ [('c','d')], [('a','c')] ])
sage: xx=G.orbit(('a','c'),"OnPairs")
sage: G.action(xx,"OnPairs")
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-4-540be1338037> in <module>()
----> 1 G.action(xx,"OnPairs")
...

Indeed, _domain_to_gap[x] needs to be applied onto such orbits. I am thinking that one should have recursive function version of
_domain_to_gap[x] and of _domain_from_gap[x] to deal with things like sets, sets of sets, etc in one go rather
than call them explicitly.

One can also (or instead) attach such a pair of functions to each action in supported_actions to do this rewriting.

nathanncohen · 2013-03-20T09:26:36Z

comment:12

The current setup allows it to be extended by the user. One can install via gap.eval() a GAP function, say, "OnBlah", and then use it. You can't do this with a module variable.

Well, if a action is being used that is not already in the source code, then there is no way for Sage to guess how to translate the result before returning it, is there ?

Otherwise we could just get rid of this list, cross our fingers when GAP is fed with something we ha not thought of, as it would raise an Exception in the worst case ?..

sure this can be done as you prefer. However, there is a more serious issue with self.action:

Arg. Right :-/

Indeed, _domain_to_gap[x] needs to be applied onto such orbits. I am thinking that one should have recursive function version of
_domain_to_gap[x] and of _domain_from_gap[x] to deal with things like sets, sets of sets, etc in one go rather
than call them explicitly.

One can also (or instead) attach such a pair of functions to each action in supported_actions to do this rewriting.

Hmmmm... I don't like it very much to be honest... In these situations I think that a bit of code duplication is better than a weird generic way to handle it.

Nathann

dimpase · 2013-03-20T16:43:43Z

comment:13

I just added a new patch (to be applied on top of the rest) that solves these issues. Please have a look if you like it. (It still needs to be cleaned a bit, and more tests ought to be added). It doesn't use the supported_actions list.

nathanncohen · 2013-03-20T17:46:10Z

comment:14

HMmmmmmmmmm :-/

I'm sorry to say this because I like that code, but I just fixed doctests in homology/simplicial_complex where an automorphism group is defined over the elements of a simplicial complex... And I am afraid that you will find both 'a', 'b', and ['a','b'] as elements of the domain :-/

Nathann

dimpase · 2013-03-21T00:51:03Z

comment:15

Replying to @nathanncohen:

HMmmmmmmmmm :-/

I'm sorry to say this because I like that code, but I just fixed doctests in homology/simplicial_complex where an automorphism group is defined over the elements of a simplicial complex... And I am afraid that you will find both 'a', 'b', and ['a','b'] as elements of the domain :-/

Well, this is trivial to fix, just swap the actions in try/except blocks in dom_to_gap internal functions.

By the way, why would one keep several actions in case of simplicial complexes, on letters and on pairs, etc? This is akin to keeping actions on vertices and edges in case of automorphisms of (simple) graphs, right? Was that a poor design in the first place?
Besides, this seems to be inefficient to keep permutations in dictionaries.

Nathann

dimpase · 2013-03-21T02:34:49Z

comment:16

Attachment: ducktype_design.patch.gz

OK, updated as I mentioned in my previous comment, with more examples added.

nathanncohen · 2013-03-21T07:44:17Z

comment:17

Helloooooooooooooo !!!

Well, this does not solve the problem either Dima. In case of doubt between an element (a,b,c) and the list of elements (a,b,c) it will return the ELEMENT (a,b,c), but it it computes the orbit of a which happens to be (a,b,c) then returning an ELEMENT (a,b,c) instead of the list (a,b,c) is a mistake too :-/

Nathann

vbraun · 2013-04-11T11:50:03Z

Changed author from Nathann Cohen to Nathann Cohen, Volker Braun

vbraun · 2013-04-11T11:50:03Z

Reviewer: Volker Braun

vbraun · 2013-04-11T13:02:31Z

comment:42

I've cleaned up some stuff and beautified the output containers (as we talked about before):

sage: S3 = groups.permutation.Symmetric(3) 
sage: S3.orbit((1,2), action = "OnSets") 
({1, 2}, {2, 3}, {1, 3}) 
sage: S3.orbit((1,2), action = "OnTuples") 
((1, 2), (2, 3), (2, 1), (3, 1), (1, 3), (3, 2))

I'm fine with everything else, so if you agree with the reviewer patch feel free to set it to positive review.

For the patchbot:
Apply trac_14291-v2.patch, trac_14291_reviewer.patch

nathanncohen · 2013-04-11T13:12:51Z

comment:43

Helloooooooooooooooo !!!

There is a "permutatino" somewhere. Could you also replace x = sorted(x) with ``x.sort()` ?

This being said, your patch does not apply on my version of Sage... But I still use beta1, perhaps that's the reason why.

Nathann

vbraun · 2013-04-11T18:22:57Z

Attachment: trac_14291_reviewer.2.patch.gz

Updated patch

vbraun · 2013-04-11T18:23:31Z

comment:44

Ok, fixed. Applies cleanly on sage-5.9.beta5.

vbraun · 2013-04-11T19:35:50Z

comment:46

Ok all doctests pass on sage-5.9.beta5.

Patchbot:
Apply trac_14291-v2.patch, trac_14291_reviewer.patch

nathanncohen · 2013-04-11T21:38:33Z

comment:47

Ok all doctests pass on sage-5.9.beta5.

Doesn't apply on my beta5 :-/

Do you have anything else applied ?

Nathann

vbraun · 2013-04-11T21:54:23Z

comment:48

Ok was based on an older version of your patch (we can't switch to git fast enough ;-)

Works now.

nathanncohen · 2013-04-11T21:59:58Z

comment:49

Well, then... :-)

Nathann

dimpase · 2013-04-12T06:54:34Z

comment:51

I'm glad to hear that it's done, and sorry for dropping silent on this - too many deadlines lately.

Dima

jdemeyer · 2013-04-12T09:09:34Z

comment:52

The documentation doesn't build properly:

dochtml.log:[groups   ] /mazur/release/merger/sage-5.10.beta0/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup.py:docstring of sage.groups.perm_gps.permgroup.PermutationGroup_generic.orbit:12: ERROR: Unknown target name: "http://www.gap-system.org/manuals/doc/ref/chap41.html".

vbraun · 2013-04-12T10:21:32Z

comment:53

I've replaced the link (which is not stable as the GAP chapter numbers can change) with a reference to our gap.help('Group Actions') command.

vbraun · 2013-04-12T10:24:26Z

Attachment: trac_14291_reviewer.patch.gz

Updated patch

jdemeyer · 2013-04-15T08:43:51Z

Merged: sage-5.10.beta0

nathanncohen · 2013-04-15T08:50:54Z

comment:55

Cooooooooool :-D

Nathann

dimpase · 2013-04-27T05:34:57Z

comment:56

Shouldn't "OnSets" return sorted things? See e.g. the related issue on #14283.

nathanncohen mannequin added this to the sage-5.9 milestone Mar 17, 2013

nathanncohen mannequin added c: group theory labels Mar 17, 2013

nathanncohen mannequin assigned wdjoyner Mar 17, 2013

nathanncohen mannequin added the s: needs review label Mar 17, 2013

This comment has been minimized.

Sign in to view

nathanncohen mannequin added s: needs work and removed s: needs review labels Mar 19, 2013

This comment has been minimized.

Sign in to view

dimpase added s: needs review and removed s: needs work labels Mar 21, 2013

This comment has been minimized.

Sign in to view

nathanncohen mannequin added s: positive review and removed s: needs review labels Apr 11, 2013

jdemeyer modified the milestones: sage-5.9, sage-5.10 Apr 12, 2013

jdemeyer added s: needs work and removed s: positive review labels Apr 12, 2013

vbraun added s: positive review and removed s: needs work labels Apr 12, 2013

jdemeyer removed the s: positive review label Apr 15, 2013

jdemeyer closed this as completed Apr 15, 2013

This was referenced May 7, 2013

M22 and Cameron graph constructors #14283

Closed

Automorphism group with labeled vertices #14319

Closed

Orbits of tuples and sets #14291

Orbits of tuples and sets #14291

Comments

nathanncohen mannequin commented Mar 17, 2013

nathanncohen mannequin commented Mar 17, 2013

dimpase commented Mar 17, 2013

nathanncohen mannequin commented Mar 17, 2013

nathanncohen mannequin commented Mar 17, 2013

dimpase commented Mar 19, 2013

nathanncohen mannequin commented Mar 19, 2013

This comment has been minimized.

dimpase commented Mar 19, 2013

nathanncohen mannequin commented Mar 19, 2013

dimpase commented Mar 19, 2013

nathanncohen mannequin commented Mar 19, 2013

This comment has been minimized.

nathanncohen mannequin commented Mar 19, 2013

dimpase commented Mar 19, 2013

nathanncohen mannequin commented Mar 20, 2013

dimpase commented Mar 20, 2013

nathanncohen mannequin commented Mar 20, 2013

dimpase commented Mar 21, 2013

dimpase commented Mar 21, 2013

nathanncohen mannequin commented Mar 21, 2013

vbraun commented Apr 11, 2013

vbraun commented Apr 11, 2013

This comment has been minimized.

vbraun commented Apr 11, 2013

nathanncohen mannequin commented Apr 11, 2013

vbraun commented Apr 11, 2013

vbraun commented Apr 11, 2013

vbraun commented Apr 11, 2013

nathanncohen mannequin commented Apr 11, 2013

vbraun commented Apr 11, 2013

nathanncohen mannequin commented Apr 11, 2013

dimpase commented Apr 12, 2013

jdemeyer commented Apr 12, 2013

vbraun commented Apr 12, 2013

vbraun commented Apr 12, 2013

jdemeyer commented Apr 15, 2013

nathanncohen mannequin commented Apr 15, 2013

dimpase commented Apr 27, 2013