Re: [sage-combinat-devel] Re: Drawings for Permutations -- how would you plot them ?
> group theorists would normally draw permutations as collection of directed > cycles, with labelled vertices. I would somewhat also expect this to be the default drawing of a permutation. Especially, when a permutation has a lot of fix points, diagram presentations get kind of messy. Imagine the permutation (1,2)(23,24) in S_n for some big n. What about an optional argument for various drawing methods that can be something like - "cycle" (my favorite for the default) - "braid" (this is the one you were proposing, Nathaan - very nice also when one can also get such a braid for multiple permutations concatenated) - "one-line" (which puts all letters 1..n on a line and then draw directed arcs to the right on top and to the left on bottom; very usefull when studying noncrossing or nonnesting permutations) - "chord-diagram" (all points on a circle and then oriented edges within the circle) Just my 2 cents, Christian -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Re: Drawings for Permutations -- how would you plot them ?
On Tuesday, 24 April 2012 23:24:14 UTC+8, Nathann Cohen wrote: > > Helloo everybody !!! > > Because of a former post on this google group [1] I created the following > patch [2]. It adds to Permutation objects a .show() method that produces > this kind of drawings [3]. > > Hence, that would be the "default way" to plot Permutations in Sage. The > thing is that it is the "natural drawing" for what I am current working on > (Permutation graphs [4]), and David says he uses them and calls them > Swapping diagrams -- which is non-standard according to him. > > group theorists would normally draw permutations as collection of directed cycles, with labelled vertices. > Well. Do you think there should be other ways to draw permutations in Sage > ? Do you have anything against that patch, which somehow makes these > drawings the "default" ones ? > If you like other type of drawings, I think it would be nice to have many > arguments to the .show() method that would yield different kind of > drawings, but the .show() method is definitely what I would look for if I > were to try to plot a drawing, so I think that these drawings should be > "reachable" through the .show() method, even if they are not the default > ones. > > Well, I'm all ears now ! Give me your thoughts, mysterious sage-combinat > crowd O_O > > Nathann > > [1] > https://groups.google.com/d/topic/sage-combinat-devel/vdfE7iaJTxs/discussion > [2] http://trac.sagemath.org/sage_trac/ticket/12872 > [3] http://trac.sagemath.org/sage_trac/attachment/ticket/12872/tmp_1.png > [4] http://en.wikipedia.org/wiki/Permutation_graph > -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To view this discussion on the web visit https://groups.google.com/d/msg/sage-combinat-devel/-/XR0Pg1JchVwJ. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Plotting permutations
On Tue, Apr 24, 2012 at 12:51:34PM +0200, Nathann Cohen wrote: >Hell !! > > I vote yes. When I teach this, I call this the swapping diagram (not > standard terminology). The number of swaps gives you the Bruhat > length, if I remember correctly, when you regard S_n as a Coxeter group. > The parity gives you the sign of the permutation, which gives you, in > turn, the > determinant of the associated matrix. It is a very useful diagram:-) > >Hmmm I just took a look at it, and it seems I just can not do this for >my own purposes. I mean, this diagram can be written, but Permutations >objets basically *cannot* store a permutation between anything different >from 1 n >Well, it just supposes that the elements in the permutation have some >"natural linear ordering", which is the one given by the '<' python >operator. Here is the code from Permutation.inversions : > p = self[:] >inversion_list = [] >for i in range(len(p)): >for j in range(i+1,len(p)): >if p[i] > p[j]: >#inversion_list.append((p[i],p[j])) >inversion_list.append([i,j]) >return inversion_list >So it looks like I cannot trust it with my strings, for instance :-/ >I will write this diagram anyway. It can prove useful to me later, and it >looks like you could use it anyway ^^; You might want to use permutations from the symmetric group instead:: sage: S = SymmetricGroup(10) sage: x = S.random_element() sage: x.inversions() [(2,3), (2,4), (2,5), (4,5), (3,5), (1,5), (2,6), (4,6), (3,6), (1,6), (5,6), (2,7), (4,7), (3,7), (1,7), (2,8), (4,8)] It has been implemented recently by Mark, and it will work for any Coxeter group. Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: Do we want a metaclass framework?
On Tue, Apr 24, 2012 at 07:23:27PM +, Simon King wrote: > OK. But I think priority should be given to cythonization of the existing > metaclasses. Namely, Florent found out how one can produce a cdef'd > metaclasses, so that its instances (thus, usual classes) inherit the fast > methods (like __call__). One can cdefine NestedClassMetaclass and > derive from it a cdefined ClasscallMetaclass (my patch isn't posted > yet). Together with some tricks that Florent presented in his original > patch at #12808, one should get a considerable speedup in creation of > classes. +1 > Also I found that one can simply rename sage/structure/dynamic_class.py > into sage/structure/dynamic_class.pyx -- that alone should yield some > speedup. And then one can likely gain even more from using Cython more > properly. Yes, I have seen that (but see my comment on the ticket) > But independent of that, I think at some point I will try to produce > a cdefined CustomisationMetaclass. *IF* it turns out that it can compete > speed-wise, then we can still decide whether we should use it to > refactor the existing metaclasses. +1 Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Re: Do we want a metaclass framework?
Hi Nicolas! On 2012-04-24, Nicolas M. Thiery wrote: > On Mon, Apr 23, 2012 at 05:59:04AM -0700, Simon King wrote: >> Hence, >>class MyClass(Parent): >>__metaclass__ = CustomisationMetaclass >>@staticmethod >>def __classadd__(... >> should suffice. > > I like this variant because it encapsulates the technical metaclass > details. So we can easily change the implementation later on if we > change our mind or find a better approach. OK. But I think priority should be given to cythonization of the existing metaclasses. Namely, Florent found out how one can produce a cdef'd metaclasses, so that its instances (thus, usual classes) inherit the fast methods (like __call__). One can cdefine NestedClassMetaclass and derive from it a cdefined ClasscallMetaclass (my patch isn't posted yet). Together with some tricks that Florent presented in his original patch at #12808, one should get a considerable speedup in creation of classes. Also I found that one can simply rename sage/structure/dynamic_class.py into sage/structure/dynamic_class.pyx -- that alone should yield some speedup. And then one can likely gain even more from using Cython more properly. But independent of that, I think at some point I will try to produce a cdefined CustomisationMetaclass. *IF* it turns out that it can compete speed-wise, then we can still decide whether we should use it to refactor the existing metaclasses. Best regards, Simon -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: Do we want a metaclass framework?
On Mon, Apr 23, 2012 at 05:59:04AM -0700, Simon King wrote: > In CustomisationMetaclass, it should not be needed to explicitly state > which methods are to be customised. Instead, CustomisationMetaclass > should look if it finds a method named "__class__" and would > *automatically* customize type.__bla__. > > Hence, >class MyClass(Parent): >__metaclass__ = CustomisationMetaclass >@staticmethod >def __classadd__(... > should suffice. I like this variant because it encapsulates the technical metaclass details. So we can easily change the implementation later on if we change our mind or find a better approach. Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: Do we want a metaclass framework?
On Mon, Apr 23, 2012 at 05:48:10AM -0700, Simon King wrote:
> ...
>
> Our current metaclasses all work by overriding a "magical" method of
> type, or adding a "magical" method to type. Ideally, this should be in
> a customisable way. In some cases, we want to override not just one
> method. Currently, each combination of customised methods requires to
> write a new metaclass. But why not have just *one* metametaclass
> "CustomisationMetaclass", such that
> CustomisationMetaclass("init","get","reduce") returns a metaclass that
> allows customisation of three methods?
An alternative would be to have a single metaclass, subclass of type,
that adds hooks to enable at once all special methods for classes.
Pros:
- It's simple
- It pushes toward eventually having all those hooks directly in type
- It is similar to what happens for objects: all hooks are directly
available; you just implement those that you need.
Inconvenient:
- If a class does not use a hook, does it still pay an overhead for
the handling of this hook? For most hooks, that's irrelevant: if a
class does not use the __classmul__ hook it won't use the syntax A*B
either. But a couple of hooks like __classcall__, __classinit__
could slow basic usage.
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil"
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Drawings for Permutations -- how would you plot them ?
> I typically draw them top-to-bottom. I've seen them called "string > diagrams" by people in pattern avoidance. +1 to that. That is actually what the patch does by default, but David told me he preferred to have them in this direction, so you can actually do both with the patch. This way everybody is happy :-) Nathann -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Drawings for Permutations -- how would you plot them ?
I typically draw them top-to-bottom. I've seen them called "string diagrams" by people in pattern avoidance. On Tue, Apr 24, 2012 at 8:24 AM, Nathann Cohen wrote: > Helloo everybody !!! > > Because of a former post on this google group [1] I created the following > patch [2]. It adds to Permutation objects a .show() method that produces > this kind of drawings [3]. > > Hence, that would be the "default way" to plot Permutations in Sage. The > thing is that it is the "natural drawing" for what I am current working on > (Permutation graphs [4]), and David says he uses them and calls them > Swapping diagrams -- which is non-standard according to him. > > Well. Do you think there should be other ways to draw permutations in Sage ? > Do you have anything against that patch, which somehow makes these drawings > the "default" ones ? > If you like other type of drawings, I think it would be nice to have many > arguments to the .show() method that would yield different kind of drawings, > but the .show() method is definitely what I would look for if I were to try > to plot a drawing, so I think that these drawings should be "reachable" > through the .show() method, even if they are not the default ones. > > Well, I'm all ears now ! Give me your thoughts, mysterious sage-combinat > crowd O_O > > Nathann > > [1] https://groups.google.com/d/topic/sage-combinat-devel/vdfE7iaJTxs/discussion > [2] http://trac.sagemath.org/sage_trac/ticket/12872 > [3] http://trac.sagemath.org/sage_trac/attachment/ticket/12872/tmp_1.png > [4] http://en.wikipedia.org/wiki/Permutation_graph > > -- > You received this message because you are subscribed to the Google Groups > "sage-combinat-devel" group. > To post to this group, send email to sage-combinat-devel@googlegroups.com. > To unsubscribe from this group, send email to > sage-combinat-devel+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/sage-combinat-devel?hl=en. -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Drawings for Permutations -- how would you plot them ?
Helloo everybody !!! Because of a former post on this google group [1] I created the following patch [2]. It adds to Permutation objects a .show() method that produces this kind of drawings [3]. Hence, that would be the "default way" to plot Permutations in Sage. The thing is that it is the "natural drawing" for what I am current working on (Permutation graphs [4]), and David says he uses them and calls them Swapping diagrams -- which is non-standard according to him. Well. Do you think there should be other ways to draw permutations in Sage ? Do you have anything against that patch, which somehow makes these drawings the "default" ones ? If you like other type of drawings, I think it would be nice to have many arguments to the .show() method that would yield different kind of drawings, but the .show() method is definitely what I would look for if I were to try to plot a drawing, so I think that these drawings should be "reachable" through the .show() method, even if they are not the default ones. Well, I'm all ears now ! Give me your thoughts, mysterious sage-combinat crowd O_O Nathann [1] https://groups.google.com/d/topic/sage-combinat-devel/vdfE7iaJTxs/discussion [2] http://trac.sagemath.org/sage_trac/ticket/12872 [3] http://trac.sagemath.org/sage_trac/attachment/ticket/12872/tmp_1.png [4] http://en.wikipedia.org/wiki/Permutation_graph -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Plotting permutations
Hell !! I vote yes. When I teach this, I call this the swapping diagram (not > standard terminology). The number of swaps gives you the Bruhat > length, if I remember correctly, when you regard S_n as a Coxeter group. > The parity gives you the sign of the permutation, which gives you, in > turn, the > determinant of the associated matrix. It is a very useful diagram:-) > Hmmm I just took a look at it, and it seems I just can not do this for my own purposes. I mean, this diagram can be written, but Permutations objets basically *cannot* store a permutation between anything different from 1 n Well, it just supposes that the elements in the permutation have some "natural linear ordering", which is the one given by the '<' python operator. Here is the code from Permutation.inversions : p = self[:] inversion_list = [] for i in range(len(p)): for j in range(i+1,len(p)): if p[i] > p[j]: #inversion_list.append((p[i],p[j])) inversion_list.append([i,j]) return inversion_list So it looks like I cannot trust it with my strings, for instance :-/ I will write this diagram anyway. It can prove useful to me later, and it looks like you could use it anyway ^^; It will be ticket #12872. Nathann -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Plotting permutations
On Tue, Apr 24, 2012 at 3:46 AM, Nathann Cohen wrote: > Helloo everyody !!! > > I am writing a patch for the recognition of Permutation graphs (and > comparability graphs, actually), and I thought that it would be nice > to have some way to plot the permutations built this way. Given a > permutation p on 1...n, you get the permutation graph by linking > together two vertices ij such that i p(j). Hence the kind > of plot I have in mind is the one you can see on the top-right corner > of his page : > > http://en.wikipedia.org/wiki/Permutation_graph > > I intended to write it, but there are two questions that need an > answer before doing that > > 1) Is it aready implemented in Sage somewhere ? I did not see it, but well :-) > 2) Is it useful to add it as a method of Permutation ? That is, should I vote yes. When I teach this, I call this the swapping diagram (not standard terminology). The number of swaps gives you the Bruhat length, if I remember correctly, when you regard S_n as a Coxeter group. The parity gives you the sign of the permutation, which gives you, in turn, the determinant of the associated matrix. It is a very useful diagram:-) > it be implemented there or rather as a part of my recognition > algorithm, if it is only of interest for graph theoreticians ? > > Thanks ! :-) > > Nathann > > -- > You received this message because you are subscribed to the Google Groups > "sage-combinat-devel" group. > To post to this group, send email to sage-combinat-devel@googlegroups.com. > To unsubscribe from this group, send email to > sage-combinat-devel+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/sage-combinat-devel?hl=en. > -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Plotting permutations
Hell !!!
The set {(i,j) | i p(j)} is called the set of the inversion of
> p
> and is in Sage. Rather than the Graph, we use the matrix associated to it
under the name Rothe diagram or inversion diagram. We had it in
> MuPAD-Combinat
> but it wasn't ported to Sage. See eg
>
>
>
Oh nice, so you already have your own representation for it !
It is closely related to the Lehmer code of the permutation which is in
> sage.
>
Nice too. It stores the permutation by counting the inversions for each
element. Nice, nice :-)
> The algorithm I used to teach my Master students works as follows: Build
> an
> orientation of the complete graph K_n as follows: for i oriented
>* j -> i if (i,j) is an inversion (ie is in your Graph)
>* i -> j else
> Then the inversion set (or the candidate permutation graph) comes from a
> permutation if the resulting orientation of K_n is acyclic. Is it what you
> want to implement (or maybe an optimization of it) ?
>
Ahahaahah ! You really scared me there ! That's what I have to pay for
staying too often in the world of graph theoreticians... I'm trying to get
out sometimes, but it really is scary outside. Once in a while you ask a
question which would be thought of HARD for people aroun you, a question
who everybody on the other side think is totally trivial. Christian Stump
did that to me just before the CNRS hearings ! :-D
Well, in this case I am somehow saved by luck... More or less :-)
The algorithm I want to implement does that, it is true. For a few seconds
I wondered why it was so easy for you while the graph papers are rather
nontrivial, and actually Yeah, I want to write a recognition algorithm
for that, only without knowing the names of the vertices at first. That's
the difference between the graph problem and your permutation problem, and
the reason why we seem to have a harder time with it than you do.
In our version of it, here is an example of the set of inversions that you
can be given :
[['Patience', 'Fraise'], ['Patience', 'Lampadaire'], ['Patience',
'Ressort'], ['Patience', 'Encephalogramme'], ['Fraise', 'Lampadaire'],
['Fraise', 'Ressort'], ['Fraise', 'Encephalogramme'], ['Ressort',
'Encephalogramme']]
Now you have to find out how the elements 'Fraise', 'Lampadaire',
'Ressort', 'Encephalogramme', 'Patience' should be ordered (labelled from 1
to 5), then to find out which permutation realizes this set of inversions.
Of course, here is how I generated it :
sage: e = ['Fraise', 'Lampadaire', 'Ressort', 'Encephalogramme', 'Patience']
sage: p = Permutations(5).random_element()
sage: map(lambda x : map(lambda y : e[y-1], x), p.inversions())
[['Patience', 'Fraise'], ['Patience', 'Lampadaire'], ['Patience',
'Ressort'], ['Patience', 'Encephalogramme'], ['Fraise', 'Lampadaire'],
['Fraise', 'Ressort'], ['Fraise', 'Encephalogramme'], ['Ressort',
'Encephalogramme']]
S... Yep, the algorithm will do that too, but even if I get to write it
properly (with data structures, time and sweat. For the moment I just have
a greedy implementation) it will be much better to solve your version of it
with your own algorithm. Perhaps it is also possible to plug both versions
at once inside of a from_inversion_set function, as your permutations are
supposed to deal with any kind of elements. But it will be mch slower
my way, whatever happens :-)
> Now, to answer your question, I certainly would vote +1 on having a
> Permutation.from_inversions methods which raise an error if the parameter
> is
> not a proper inversion set. Alternatively, "is_inversion_set" returning
> True
> or False is good too.
>
Ok ! And so, what about these drawings ? Do we put them inside of
Permutation (at the same time Rothe diagrams and the one I sent you), do
you think it should stay in the graph library ?
Cheers,
>
Thaaanks ! :-)
Nathann
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/sage-combinat-devel/-/IXGv_IYXgXYJ.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Generating many classes, some of them with additional methods
Helloo Everybody !! The subject is not very clear, but given a few more lines I can make it a bit more explicit. Here is my problem : When #11880 we will have in Sage a database of graph classes. That is objects representing things like "Interval Graphs", "Planar Graphs", things like that. This database contains a HUGE number of classes (around 1000), and some of these graph classes are more famous than others. In particular, we have in Sage algorithms to tests whether a graph is planar, or an interval graph. Hence it would be nice to be able to use these methods like that : g in graph_classes.PlanarGraphs g in graph_classes.IntervalGraph To do so, the recognition methods should be reached by the __in__ method of each of those graph classes. And here is where the problem lies : I have on one hand a way to build Sage objects representing graph classes, and on the other hand recognition algorithms for SOME of them. How should I make the link between the two ? 1) Should any object representing a Graph class have a __in__ method which checks whether the class represented by the object has a recognition algorithm listed in a dictionnary somewhere ? 2) Should the graph classes objects be generated in such a way (how ?) such that its __in__ method is automatically the good one ? I expect you already had to deal with problems like that in your code, so just in case you already found a great answer to that. ;-) Thank yo !!! Nathann -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Plotting permutations
Hi Nathann,
> I am writing a patch for the recognition of Permutation graphs (and
> comparability graphs, actually), and I thought that it would be nice
> to have some way to plot the permutations built this way. Given a
> permutation p on 1...n, you get the permutation graph by linking
> together two vertices ij such that i p(j). Hence the kind
> of plot I have in mind is the one you can see on the top-right corner
> of his page :
>
> http://en.wikipedia.org/wiki/Permutation_graph
>
> I intended to write it, but there are two questions that need an
> answer before doing that
> 1) Is it aready implemented in Sage somewhere ? I did not see it, but well :-)
The set {(i,j) | i p(j)} is called the set of the inversion of p
and is in Sage. Rather than the Graph, we use the matrix associated to it
under the name Rothe diagram or inversion diagram. We had it in MuPAD-Combinat
but it wasn't ported to Sage. See eg
It is closely related to the Lehmer code of the permutation which is in sage.
> 2) Is it useful to add it as a method of Permutation ? That is, should
> it be implemented there or rather as a part of my recognition
> algorithm, if it is only of interest for graph theoreticians ?
The algorithm I used to teach my Master students works as follows: Build an
orientation of the complete graph K_n as follows: for i i if (i,j) is an inversion (ie is in your Graph)
* i -> j else
Then the inversion set (or the candidate permutation graph) comes from a
permutation if the resulting orientation of K_n is acyclic. Is it what you
want to implement (or maybe an optimization of it) ?
Now, to answer your question, I certainly would vote +1 on having a
Permutation.from_inversions methods which raise an error if the parameter is
not a proper inversion set. Alternatively, "is_inversion_set" returning True
or False is good too.
Cheers,
Florent
> Thanks ! :-)
>
> Nathann
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-combinat-devel" group.
> To post to this group, send email to sage-combinat-devel@googlegroups.com.
> To unsubscribe from this group, send email to
> sage-combinat-devel+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/sage-combinat-devel?hl=en.
--
Florent Hivert
---
Il y a trois sortes de gens dans le monde : ceux qui savent compter et
ceux qui ne savent pas.
There are three kinds of people in the world: those who can count,
and those who cannot.
---
Professeur, LRI, Univ. Paris Sud 11, CNRS.
Bureau 38, Laboratoire de Recherche en Informatique (UMR CNRS 8623)
Bâtiment 650, Université Paris Sud 11, 91405 ORSAY CEDEX
Tél: 01-69-15-65-99
http://www.lri.fr/~hivert
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Plotting permutations
Helloo everyody !!! I am writing a patch for the recognition of Permutation graphs (and comparability graphs, actually), and I thought that it would be nice to have some way to plot the permutations built this way. Given a permutation p on 1...n, you get the permutation graph by linking together two vertices ij such that i p(j). Hence the kind of plot I have in mind is the one you can see on the top-right corner of his page : http://en.wikipedia.org/wiki/Permutation_graph I intended to write it, but there are two questions that need an answer before doing that 1) Is it aready implemented in Sage somewhere ? I did not see it, but well :-) 2) Is it useful to add it as a method of Permutation ? That is, should it be implemented there or rather as a part of my recognition algorithm, if it is only of interest for graph theoreticians ? Thanks ! :-) Nathann -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
