[sage-combinat-devel] Re: Generalized Permutations
On 2012-11-28, Nathann Cohen nathann.co...@gmail.com wrote: --bcaec5171ecd442ad804cf90b70b Content-Type: text/plain; charset=ISO-8859-1 Helloo !! I guess it's a perfect illustration of **limits** of the object-oriented approach. RSK takes (p,q) in PxQ and outputs (a,b) in AxB. Does this mean we have to knock ourselves out creaing classes for each pair of classes P,Q we have? NOooo ! We have metaclasses for that :-P is it indended as sarcasm? (as you know, it's hard to detect in written correspondence) Little I know about metaclasses in Python does not correspond to anything in Sage (I hear it is used in pickling, is it all?), and I wonder whether there is any documentation on this, if at all. (and as far as I know Python does not have anything resembling Haskell's algebraic data types). Cheers, Dima -- 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: Generalized Permutations
Travis Scrimshaw tsc...@ucdavis.edu writes: Martin, You mentioned that you had code for variants of RSK, could you repost/reference that? I have no time until next week for cleaning but it's a start. The domino insertion is currently only there as code for fricas (done by a student, not myself). The algorithm appears in a paper by Thomas Lam. The main routines are grow and shrink. Grow takes a filling (eg. a matrix with entries in N, but you can take any Ferrers shape) and a rule and yields the partitions. Note however that this is not a very fast way to do the four variants of RSK, rather it is Fomin's growth diagrams in almost full generality. To get these, you have to do m = grow(filling, Partition([]), Robinson_Schensted_Knuth_forward) and then read the partitions along the top row to get the Q-symbol, and along the right column to get the P-symbol. shrink produces the filling given the borders. I am also not claiming that the data structures are perfect. I just notice that I only implemented rules for RSK and Burge. However, to get the other two is very easy, they are spelled out in Christian Krattenthaler's paper. Best, Martin -- 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. growth-for-sage.sage Description: Binary data
[sage-combinat-devel] Re: Generalized Permutations
On 2012-11-27, Travis Scrimshaw tsc...@ucdavis.edu wrote: --=_Part_468_5000489.1354057101700 Content-Type: text/plain; charset=ISO-8859-1 Hey everyone, I've been trying to figure out how to handle generalized permutations (a.k.a. two-line arrays, bi-words, ...) since we want Permutation() to only accept input from 1 to n. A typical misuse of Permutation is in sage/combinat/integer_vector_weighted.py where nothing prevents one to return lists all the time. Cf. e.g. the relevant part of http://trac.sagemath.org/sage_trac/attachment/ticket/13742/trac_13742_reviewer1.patch Yes, and the RSK stuff is a more tricky one. I have a stupid question: why can't one just use lists? One should not overdesign. What are the real reasons for GeneralizedPermutation to come? E.g. to have a special class to just handle a pair of lists of equal length is a big an overdesign to me. And if you need the first list to be ordered, use a pair (set,list) In particular, in a clean 5.5.rc0, the permutations code will perform RSK (and the inverse) on one-line arrays with a standard recording tableau. Currently trac_8392-check_permutation-ts.patch tweaks the inverse to return a generalized permutation, however I would like to know how I should go about structuring these classes? Here's my current thoughts: - Create a class Biword which is just two finite words of the same length. - Create a class GeneralizedPermutation which inherits from Biword and will check necessary conditions (e.g. support is a totally ordered alphabet, weakly increasing in top row, etc.). - Refactor Permutation_class so that it inherits from Finite_word (I've talked about this with Anne, and she was favorable to this). - Have a coercion map from Word (or Permutation) to GeneralizedPermutation - Implement the various RSK functions in respective classes. - Some abstract class which holds methods common to GeneralizedPermutation and Permutation. Thanks, Travis -- 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: Generalized Permutations
Helloo everybody !!! since we want Permutation() to only accept input from 1 to n. In particular Well, I do not want Permutations to be defined on 1...n only. First, because I ideally would like them to be defined on 0...(n-1), and then because of course I would like them to be defined on any Sage object. I want Permutation methods to return valid results, though. And the only practical way we have to do this (unless somebody with real knowledge of all methods modifies them so that it works on arbitrary permutations) is to make sure that the input matches what the methods assume. What I think is the most important, though, is to have some Cython Permutation class, which would be a fast backend to your GeneralisedPermutation, or just Python Permutations.. And those would naturally be 0...n-1 s they would be integer arrays : i.e. the most natural implementation of a Permutation. At Python-level we could detect on-the-fly whether the permutations are integer ones (0...n-1, i.e. if we can store them using the backend only) or generalized ones. I have a stupid question: why can't one just use lists? One should not overdesign. What are the real reasons for GeneralizedPermutation to come? E.g. to have a special class to just handle a pair of lists of equal length is a big an overdesign to me. And if you need the first list to be ordered, use a pair (set,list) I totally agree with that. Many graph functions are meant to return sets of vertices, but returning a list of them makes sense. The only exception to that, I believe, are the feedback_vertex_set methods which will have to be fixed eventually :-) 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/-/JWJ_JfvAjr0J. 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: Generalized Permutations
On 11/28/12 5:35 AM, Dima Pasechnik wrote: On 2012-11-27, Travis Scrimshaw tsc...@ucdavis.edu wrote: --=_Part_468_5000489.1354057101700 Content-Type: text/plain; charset=ISO-8859-1 Hey everyone, I've been trying to figure out how to handle generalized permutations (a.k.a. two-line arrays, bi-words, ...) since we want Permutation() to only accept input from 1 to n. A typical misuse of Permutation is in sage/combinat/integer_vector_weighted.py where nothing prevents one to return lists all the time. Cf. e.g. the relevant part of http://trac.sagemath.org/sage_trac/attachment/ticket/13742/trac_13742_reviewer1.patch Yes, and the RSK stuff is a more tricky one. I have a stupid question: why can't one just use lists? One should not overdesign. What are the real reasons for GeneralizedPermutation to come? E.g. to have a special class to just handle a pair of lists of equal length is a big an overdesign to me. And if you need the first list to be ordered, use a pair (set,list) Hi Dima, This last suggestion would indeed be a good idea. Where would you put the code in this case? The input would be a (set,list) and the output a pair of semistandard Young tableaux, so it is not so obvious where it belongs. Best, Anne -- 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: Generalized Permutations
On 2012-11-28, Anne Schilling a...@math.ucdavis.edu wrote: On 11/28/12 5:35 AM, Dima Pasechnik wrote: On 2012-11-27, Travis Scrimshaw tsc...@ucdavis.edu wrote: --=_Part_468_5000489.1354057101700 Content-Type: text/plain; charset=ISO-8859-1 Hey everyone, I've been trying to figure out how to handle generalized permutations (a.k.a. two-line arrays, bi-words, ...) since we want Permutation() to only accept input from 1 to n. A typical misuse of Permutation is in sage/combinat/integer_vector_weighted.py where nothing prevents one to return lists all the time. Cf. e.g. the relevant part of http://trac.sagemath.org/sage_trac/attachment/ticket/13742/trac_13742_reviewer1.patch Yes, and the RSK stuff is a more tricky one. I have a stupid question: why can't one just use lists? One should not overdesign. What are the real reasons for GeneralizedPermutation to come? E.g. to have a special class to just handle a pair of lists of equal length is a big an overdesign to me. And if you need the first list to be ordered, use a pair (set,list) Hi Dima, This last suggestion would indeed be a good idea. Where would you put the code in this case? The input would be a (set,list) and the output a pair of semistandard Young tableaux, so it is not so obvious where it belongs. I guess it's a perfect illustration of **limits** of the object-oriented approach. RSK takes (p,q) in PxQ and outputs (a,b) in AxB. Does this mean we have to knock ourselves out creaing classes for each pair of classes P,Q we have? And note that P and Q is so general that there are undoubtly zillions of functions out there which can take P and Q and output something that has absolutely nothing to do with RSK, SSYTs, even combinatorics in general. Just put RSK in global scope (or, better, in a package, which incorporates stuff that deals with A and B, which here is much more restrictive than P and Q). Or, if you must go OO, you can think of RSK as a constructor for elements of AxB (do you have a class for pairs of tableaux already?). In this way you don't need to worry about a new class for PxQ, at least. HTH, Dima Best, Anne -- 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: Generalized Permutations
Helloo !! I guess it's a perfect illustration of **limits** of the object-oriented approach. RSK takes (p,q) in PxQ and outputs (a,b) in AxB. Does this mean we have to knock ourselves out creaing classes for each pair of classes P,Q we have? NOooo ! We have metaclasses for that :-P And note that P and Q is so general that there are undoubtly zillions of functions out there which can take P and Q and output something that has absolutely nothing to do with RSK, SSYTs, even combinatorics in general. There's nothing outside of combinatorics. Just put RSK in global scope (or, better, in a package, which incorporates stuff that deals with A and B, which here is much more restrictive than P and Q). Err... Or just define it as a function, inside of a module ? This way everybody can have function (you know, the thing that is a method when you have no object in front of it). Like a library, a simple library With functions inside You know, just C-style :-P Or, if you must go OO, you can think of RSK as a constructor for elements of AxB (do you have a class for pairs of tableaux already?). In this way you don't need to worry about a new class for PxQ, at least. The thing is that what we know how to do is build meta classes. That's our job, that's what we do best, that's how we make money. If nobody needs metaclasses, what we should do is convince them that we they DO need metaclasses :-P 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.
[sage-combinat-devel] Re: Generalized Permutations
On 2012-11-28, Nathann Cohen nathann.co...@gmail.com wrote: --bcaec5171ecd442ad804cf90b70b Content-Type: text/plain; charset=ISO-8859-1 Helloo !! I guess it's a perfect illustration of **limits** of the object-oriented approach. RSK takes (p,q) in PxQ and outputs (a,b) in AxB. Does this mean we have to knock ourselves out creaing classes for each pair of classes P,Q we have? NOooo ! We have metaclasses for that :-P And note that P and Q is so general that there are undoubtly zillions of functions out there which can take P and Q and output something that has absolutely nothing to do with RSK, SSYTs, even combinatorics in general. There's nothing outside of combinatorics. well, I can crosspost this to sage-nt :-) Just put RSK in global scope (or, better, in a package, which incorporates stuff that deals with A and B, which here is much more restrictive than P and Q). Err... Or just define it as a function, inside of a module ? This way yes, that's exactly what I meant when I said global scope everybody can have function (you know, the thing that is a method when you have no object in front of it). Like a library, a simple library With functions inside You know, just C-style :-P Or, if you must go OO, you can think of RSK as a constructor for elements of AxB (do you have a class for pairs of tableaux already?). In this way you don't need to worry about a new class for PxQ, at least. The thing is that what we know how to do is build meta classes. That's our job, that's what we do best, that's how we make money. If nobody needs metaclasses, what we should do is convince them that we they DO need metaclasses :-P 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.
[sage-combinat-devel] Re: Generalized Permutations
Martin, You mentioned that you had code for variants of RSK, could you repost/reference that? Thanks, Travis On Tuesday, November 27, 2012 2:58:21 PM UTC-8, Travis Scrimshaw wrote: Hey everyone, I've been trying to figure out how to handle generalized permutations (a.k.a. two-line arrays, bi-words, ...) since we want Permutation() to only accept input from 1 to n. In particular, in a clean 5.5.rc0, the permutations code will perform RSK (and the inverse) on one-line arrays with a standard recording tableau. Currently trac_8392-check_permutation-ts.patch tweaks the inverse to return a generalized permutation, however I would like to know how I should go about structuring these classes? Here's my current thoughts: - Create a class Biword which is just two finite words of the same length. - Create a class GeneralizedPermutation which inherits from Biword and will check necessary conditions (e.g. support is a totally ordered alphabet, weakly increasing in top row, etc.). - Refactor Permutation_class so that it inherits from Finite_word (I've talked about this with Anne, and she was favorable to this). - Have a coercion map from Word (or Permutation) to GeneralizedPermutation - Implement the various RSK functions in respective classes. - Some abstract class which holds methods common to GeneralizedPermutation and Permutation. Thanks, Travis -- 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/-/YT1k63Tq7lEJ. 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.
