Re: [sage-combinat-devel] Canonical form for permutation groups
to sage-combinat-devel@** > googlegroups.com . > Visit this group at http://groups.google.com/** > group/sage-combinat-devel?hl=**en<http://groups.google.com/group/sage-combinat-devel?hl=en> > . > For more options, visit > https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/opt_out> > . > > > -- Jason B. Hill http://www.jasonbhill.com | ja...@jasonbhill.com -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Re: a problem in the new permutation groups code (and a solution ?)
hink its unambiguous to define the orbit of x recursively as >> 1. use the action on domain elements if x is a domain element >> 2. otherwise, assume that the x is a list/set/... of domain elements >> >> >> >> On Thursday, March 21, 2013 3:10:38 PM UTC+1, Dima Pasechnik wrote: >>> >>> While working on >>> http://trac.sagemath.org/sage_**trac/ticket/14291<http://trac.sagemath.org/sage_trac/ticket/14291>, >>> it >>> came to my attention that one can now have permutation groups acting >>> on quite arbitrary domains (the only requirement for the domain elements >>> seems to be them being hashable). >>> >>> This leads to the following kind of confusing situations: >>> suppose our permutation group G acts on, say, (1,2,3,4,(1,2),(2,3)). >>> Then things like "the orbit (1,2) under G" can be interpreted in two >>> different incompatible ways: >>> * the images under G of the pair of domain elements 1 and 2. >>> * the images under G of of the domain element (1,2). >>> >>> I can see two ways to remedy this: >>> 1) a framework with parents, etc >>> 2) "boxing" the most "primitive" elements of the domain, i.e. >>> as in our example, using ((1),(2),(3),(4),(1,2),(2,3)) instead of >>> (1,2,3,4,(1,2),(2,3)); then certainly ((1),(2)) and (1,2) are >>> different things, problem solved. >>> >>> (and certainly you can tell me that actually it's OK as it is... :)) >>> >>> IMHO, 2) is relatively easy to put into place, and 1) is tricky and >>> quite a bit of >>> work. >>> >>> Dima >>> >>> -- > You received this message because you are subscribed to the Google Groups > "sage-combinat-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-combinat-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-combinat-devel@googlegroups.com. > Visit this group at > http://groups.google.com/group/sage-combinat-devel?hl=en. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- Jason B. Hill http://www.jasonbhill.com | ja...@jasonbhill.com -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] A *wow* read O_O
Whoa. I think my laptop just got noticeably heavier by downloading that book. :-) Thanks! Jason On Mon, May 2, 2011 at 10:43 AM, Nathann Cohen wrote: > Hello everybody !!! > > I had the good idea to go "waiting_for_review_ticket"-hunting, and > fell on this one : > > http://trac.sagemath.org/sage_trac/ticket/7656 > > The ever-too-great Minh gives a link toward a mysterious web page, > which happens to be this (very expensive) book > > http://www.amazon.fr/Matters-Computational-Ideas-Algorithms-Source/dp/3642147631/ref=sr_1_1?ie=UTF8&qid=1304353267&sr=8-1 > > Luckily, the author gives the original pdf file at this address : > > http://www.jjj.de/fxt/fxtbook.pdf > > And my dear friends, if you love to implement combinatorial algorithms > (what's the point of being on this group otherwise ?), just give the > table of contents a look. > > O_O > > Nathann > > P.S. : Don't you dare touching the bitset tickets, they're all mine ! > > -- > 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. > > -- Jason B. Hill http://math.jasonbhill.com | jason.b.h...@colorado.edu -- 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: [sage-devel] permutation groups
> Please read through Robert Miller's code. It's written very cleanly > in Cython; I'd call it "appropriate for consumption". It isn't > necessarily state of the art, but it's a very good beginning. That's awesome! I should clarify: I didn't mean to say anyone's code wasn't appropriate for consumption (well, at least not Robert Miller's)... only that the available publications/whatevers that explain the algorithms appear to be. Leon's papers may be my definition of "not appropriate for consumption," but that's where I learned the theory because that's what I could find. (The Seress text has a partition backtrack section, but it is very thin.) -- Jason B. Hill http://math.jasonbhill.com | jason.b.h...@colorado.edu -- 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: [sage-devel] permutation groups
Is anyone else chiming in here planning to be in Galway next week for the De Brun workshop? I'm giving a talk related to doing such computations on more modern hardware and architectures. (I've been playing with a randomized parallel partition backtrack with C and mpi/openmp/cuda.) There was also some discussion recently among a few of us working in this area about getting our own workshop together. I'm all for that, but haven't had much time recently to chime in. > Just one question: do we have the manpower, within the Sage community, > to maintain this code in the long run? While manpower is an issue, I don't think it is the main issue. I think there are currently an appropriate number (perhaps a small number) of those that know the theory and know an acceptable language (C, Python, Cython, etc.). The main problem, as I see it, is that the majority of code, as it has existed over roughly 20 years, is nearly inaccessible. This is true especially of backtrack code. The only real exception I see to accessibility of the theory is in the partition backtrack algorithms themselves. Those simply need to be written in a language that is appropriate for consumption. As far as I know, nobody has really done this. Has anyone done this? I don't think it would be hard. (E.g., for my purposes I use a language much more like I.G. Macdonald's text... although this blurs the difference between partitions and set compositions.) Jason -- Jason B. Hill http://math.jasonbhill.com | jason.b.h...@colorado.edu -- 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: error after -combinat install
It works fine now. Thanks! -- Jason B. Hill http://math.jasonbhill.com | jason.b.h...@colorado.edu -- 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-de...@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] error after -combinat install
om sage.structure.element import is_Vector AttributeError: 'module' object has no attribute 'all' Error importing ipy_profile_sage - perhaps you should run %upgrade? WARNING: Loading of ipy_profile_sage failed. sage: -- Jason B. Hill http://math.jasonbhill.com | jason.b.h...@colorado.edu -- 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-de...@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] Matrix of a permutation
Can you clarify this a bit? Obviously, there's a difference between the product of matrices of permutations and the matrix of the product of permutations. That is, they are 'reversed.' But, multiplication in the matrices is not the same operation as the one imposed on the elements from a group. For example, take a group acting on [2,4,6] and one acting on [1,3,5] in Sage, then create the corresponding 6x6 matrices for their elements. You can of course multiply matrices from the even group with the odd group... but this has absolutely nothing to do with the multiplicative structure of either group. So, my gut instinct is that the methods for going from a permutation or a permutation group element to a matrix should be identical. (Afterall, permgroup elements and matrices themselves have no multiplicative structure... this is something given by the group that contains them. We're not translating the group structure, only the permutation structure.) Is that what you're asking? Jason On Sat, Jul 10, 2010 at 10:48 AM, Mike Hansen wrote: > Hello all, > > There is a patch a #2215 [1] that needs a (hopefully quick) design > decision. It defines _matrix_ for Permutation objects so that > matrix(p) works. I originally wrote the patch so that it was > consistent with .to_matrix(), but David Joyner thought that it should > be consistent with PermutationGroupElement (whose multiplication is > 'reversed'). > > Basically, it'd just be good to get some additional third party input > so that we can close the ticket. > > --Mike > > [1] http://trac.sagemath.org/sage_trac/ticket/2215 > > -- > 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-de...@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-de...@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-devel] Re: Fwd: [sage-combinat-devel] permutation group perspectives
Sweet! I'm assuming you're using a dictionary map? I think this could kill two birds with one stone. If we want to make Sage act more like GAP and consider the domain of a permutation group to be the collection of non-fixed points (I think we should consider subgroups separately), then even in the case when the generators contain integers, those integers could be dictionaried (I think that's a word) into a compacted list of integers. In that situation, 99% of the existing methods could be used. I have some things to add to the subgroup discussion from farther up, and I'll be back from vacation on Wednesday. Unfortunately, this will be my last computer access until then. :-( Jason B. Hill On Sun, May 30, 2010 at 3:46 PM, Mike Hansen wrote: > On Fri, May 21, 2010 at 5:58 PM, Jason B Hill > wrote: > > Can we get a list together of all of those who may be interested in > > contributing to the rewrite of permutation groups on some level? We can > move > > to an in-depth discussion and inventory. I don't want to flood the > > sage-devel list with too much, unless there are those who think the > > discussion should remain here. > > I've been working on this over the next few days, cleaning up the > code, and making permutation groups act over an "arbitrary" domain. > I'll be posting these in the next few days. > > --Mike > > -- > 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-de...@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-de...@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-devel] Fwd: [sage-combinat-devel] permutation group perspectives
On Tue, May 18, 2010 at 12:28 AM, Robert Bradshaw < rober...@math.washington.edu> wrote: > I full heartedly agree with the idea that permutation groups should be able > to act on more than just the set 1..n, using a dictionary to do the mapping > transparently to the user under the hood (and this is technically totally > feasible). I'm not as convinced that we should throw out the notion of fixed > points. For example, given Sn, n>2, I would not say all Z/2Z subgroups are > "transitive" but it sounds like you want it to. > > Good question. Your point aims at the notion that transitivity is not inherently an invariant of a group, but is a property of a specific representation. Yes, something such as a group generated by (100,101) should be considered transitive... while a group generated by (98,99)(100,101) as a single generator is clearly not transitive. They are both of course representations of Z/2Z. At present, Sage considers neither of these to be transitive. I also agree that we should not throw away the notion of fixed points. But, my argument is that fixed points of a permutation representation should be made explicit when defining the representation. So, a group generated by (2)(100,101) is not transitive while a group generated by (100,101) is. > Would it be sufficient to provide a method that, given a group, returns a > representation that keeps the permuted set names the same, but restricts the > domain to non-fixed points? > I do think this would be sufficient, yes. Keep in mind though that this should be easily restricted to subgroups and subrepresentations. Jason B Hill > > - Robert > > > On May 17, 2010, at 3:06 PM, Mike Hansen wrote: > > -- Forwarded message -- >> From: Jason B Hill >> Date: Mon, May 17, 2010 at 3:05 PM >> Subject: [sage-combinat-devel] permutation group perspectives >> To: sage-combinat-devel@googlegroups.com >> >> >> >> This comes after a discussion I had with several at Sage days 20.5 in >> Toronto relating to the underlying structure of permutation >> representations in Sage. Sorry for the length, but it does completely >> express the situation. >> >> I'll start by saying that I'm relatively new to Sage development (I'm >> from the lands of GAP and C), but I do have some time and desire to >> contribute in this area, depending on what results from this >> discussion. I've also posted a ticket (#8929) on trac.sagemath.org >> that adds some minimal functionality along these lines to the >> permutation group methods in permgroup.py. >> >> Here's my basic issue: Sage constructs permutation groups in a very >> intuitive, but arguably less robust and less mathematically consistent >> way when compared to GAP. I want to explain these differences, to >> explain why Sage's current perspective makes conducting my research in >> Sage very challenging, and also to explain how the two perspectives >> may potentially be brought together to add more functionality to >> permutation group methods in Sage than currently exist in either Sage >> or GAP. >> >> Here's an example of the same permutation group (really, a permutation >> representation or action) in Sage and in GAP: >> >> sage: G=PermutationGroup([[(2,3,4,5,6,7,8)]]) >> gap> G:=Group([(2,3,4,5,6,7,8)]); >> >> To illustrate the differences between Sage and GAP, we can consider >> transitivity: >> >> sage: G.is_transitive() >> False >> gap> IsTransitive(G); >> true >> >> This difference is caused by GAP understanding G to be a permutation >> representation acting on [2 ... 8], while Sage understands the action >> to be on the set [1 ... 8], where 1 is in the domain of the action and >> is simultaneously never moved by this specific representation. Sage >> determines the degree of a permutation group to be the largest integer >> moved by any of the generators. GAP considers the degree of a >> permutation group to be the number of non-fixed points of the >> representation. Hence, any notion of transitivity, regularity, >> primitivity, etc. will be considerably different between GAP and Sage. >> In fact, Sage currently has no is_primitive method, and I don't think >> it is possible to implement such a method consistently given Sage's >> current implementation of G.degree(). In our above example, GAP does >> rightly think that G is primitive. However, in Sage, not only do we >> have a block system / equivalence relation on the domain (composed on >> blocks having different sizes, that's bad), but the representation of >> G is not ev
[sage-combinat-devel] permutation group perspectives
o translate the non-fixed points of Sage's permutation group generators to a compacted list of integers [1 ... degree] on which the current methods could be run. This may have the added benefit of being able to define permutation actions in Sage on more than integers. (I.e., one could define a permutation action on arbitrary strings such as 'jane' and 'red'.) That would be a huge bonus over current implementations in Sage or GAP. Once the methods are run, then the dictionary could translate back and output results in the original generator language. If singleton/trivial placeholders are desired as generators in permutation actions, then entering them as [(2)] or [(joe)] should be acceptable as input as a generator. For now, I would appreciate input on this and also the patch I submitted to introduce some of these capabilities in Sage's current implementation of permutation groups. Brevity is a virtue I do not have. Sorry about that. Jason B. Hill -- 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-de...@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.
