On 2013-03-26, Nathann Cohen <nathann.co...@gmail.com> wrote:
> --bcaec54315d24dec2004d8cfa610
> Content-Type: text/plain; charset=ISO-8859-1
>
> Helloooooooooooooooooooooo !!!
>
>> Well, unfortunately I don't know under which Seine bridge mathematicians
>> are most
>> welcome :-)
>
> Ahahahah. I felt so shocked when I first learnt that Paris did not have the
> only one O_O
>
>> Mind you, when this part of GAP was developed, you were in primary
>> school;-),
>
> And I had more important things to do, like looking for sweets. I will not
> be held responsible.
>
>> computers were slow and weak, everything needed to be coded
>> in C or Fortran (or one would need to use Lisp, which wasn't very
>> popular in that part of computational algebra --- unfortunately);
>> naturally, some features remain hugely underdeveloped due to this. IMHO
>> a part of the GAP framework of actions which deals with tuples, subsets,
>> etc.
>> is at present more of a burden than of an advantage. (Whereas actions
>> say on cosets of a subgroup which GAP has are hugely important and hard to
>> beat)
>
> Hmmm... But then, should we patch Sage to add features or patch GAP and use
> it in Sage ? :-P
>
>> Coding more generic orbit algorithms for permutation groups
>> in a language like Python is, moreover, quite easy.
>> (By more generic---than tuples, tuples of tuples, etc---
>> I mean the action on trees with leafs labeled by
>> elements of the group domain, and with some (fixed) non-terminal node
>> might
>> carry out the structure of a set, i.e. have unordered rathen than
>> ordered neighbourhoods. E.g. you can get an action on gadgets like
>> (1,{2,3},((4,5),2,{1,6,7})); here the domain elements are numbers, but
>> this need not be a restriction.)
>> Just get yourself a queue, put there the starting element, and add the
>> new images to the other end of the queue, while computing the images of
>> the 1st in order element in the queue.
>> One is done when everything in the queue is processed
>
> Yep yep. In my world that's called a depth-first-search. But we are shy
> guys, especially when surrounded by real mathematicians.
no, DFS uses a stack, i.e. LIFO (Last In First Out), not a queue (FIFO, First
in First Out), isn't it?
>
>> All the orbit algorithm needs to know, apart from the group generators,
>> is how to compute the image is the tree "shape", i.e. no labels on the
>> nodes.
>> E.g. for the example above the shape is encoded by
>> (,{,},((,),,{,,})).
>>
>> And this can be made modular etc, as there are more actions around than
>> these which fit this pattern; so how to compute the action can be
>> specified by a function passed as a parameter. (Not sure if one also
>> needs a function to compare orbit elements for equality.)
>
> Oh. You'd give "(,{,},((,),,{,,}))" as a string parameter, parse it and use
> it to define the tree ? Ahahaha. Funny and efficient ! A bit ....
> "home-made", but I like that :-P
>
> Actually, what would have prevented me from dirtying beautiful groups with
> my out-of-place graph approach (i.e. the DFS above) is that I would have
> thought the group guys were too smart to use such things. Is that how GAP
> computes orbits ? Just a BFS ? A "set" object, hash functions for the
> group's elements, and that's all we need for a "state of the art" orbit
> method ?
and a queue. A bit of discipline never hurts :)
Otherwise, that's all is needed. But indeed, it's not totally obvious.
I know very smart people, much smarter
than me, who instead computed orbits by listing all the elements of the
group first, and applying them all...
>
>> I wrote above how I'd see this done.
>> I think it's better to encode the "usual" types of action by such a
>> pattern like above (e.g. (,{,},((,),,{,,}))).
>> Such a pattern can either be guessed/computed by Volker's rules, or
>> specified as a parameter. (And a user function to compute the action
>> can also be a parameter).
>> They could be translated into GAP actions and GAP calls, for which such
>> actions exist.
>
> Ok good point. But now I have a more pratical question : can we get #14291
> after just replacing this "action" parameter with your funny string, and
> return a "notimplementederror" when the value of action cannot be forwarded
> to GAP ?
> As it is, it is already a nice feature for humble graph theoreticians to
> compute the orbit of a pair of elements :-)
I guess this should work, but I have negative amount of time available
in the coming two weeks...
Dima
>
> Nathann
>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
