Re: [sage-devel] Re: Poset/lattice, join and join_matrix
By coincidence I just found that the function GCD_list in sage.rings.integer was coded to return one for an empty list. Fix (needs review!) at http://trac.sagemath.org/ticket/17257 Samuel -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
Nathann Cohen wrote: Yo ! This is good argument to support (only) []-style argument for several elements. Be consistent within same program. Or in Sage terms, Build a car, don't let it look like bicycle combined to tractor. :=) Btw, why gcd([]) returns zero? At least there is inconsistency with lcm([]) returning one. I guess they should both return one or raise an exception. I would say that it is because for guys doing number theory Z/2Z is associated with 2 and Z is associated with 0. Think of 0 like the infinity, or the product of all integers. Here is how I would put it: - sum([]) is zero because zero is the identity element for addition (for any x, the sum 0 + x equals x), therefore you can initialize a sum to 0, then add summands one by one, and this gets you the sum; so an empty sum is just the initial 0. - prod([]) is one because one is the identity element for multiplication (for any x, the product 1*x equals x); therefore you can initialize a product to 1, then multiply by the multiplicands one by one, and this gets you the product; so an empty product is just the initial 1. - gcd([]) is zero because zero is the identity element for gcd (for any x, gcd(0,x) equals x); therefore you can initialize a gcd to 0, then take gcd with the list elements one by one, and this gets you the gcd; so an empty gcd is just the initial 0. - lcm([]) is one because one is the identity element for lcm (for any x, lcm(1,x) equals x); therefore you can initialize an lcm to 1, then take lcm with the list elements one by one, and this gets you the lcm; so an empty lcm is just the initial 1. -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
On Mon, 27 Oct 2014, Samuel Lelievre wrote: Here is how I would put it: - gcd([]) is zero because zero is the identity element for gcd (for any x, gcd(0,x) equals x); Understood. Thanks. -- Jori Mäntysalo -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
On Mon, Oct 27, 2014 at 5:55 AM, John Cremona john.crem...@gmail.com wrote: On 27 October 2014 12:37, Nathann Cohen nathann.co...@gmail.com wrote: Yo ! This is good argument to support (only) []-style argument for several elements. Be consistent within same program. Or in Sage terms, Build a car, don't let it look like bicycle combined to tractor. :=) Btw, why gcd([]) returns zero? At least there is inconsistency with lcm([]) returning one. I guess they should both return one or raise an exception. It is not inconsistent, any more than this is: sage: sum([]) 0 sage: prod([]) 1 and the reason is essentially the same. I would say that it is because for guys doing number theory Z/2Z is associated with 2 and Z is associated with 0. Think of 0 like the infinity, or the product of all integers. I don't quite follow that but as a number theorist here is how I would explain it. If you write a loop to read in integers and output their sum, you just add each new one to the runing total, after initializing this total to: 0 Same but for products: you have to initialize to 1. Same but for gcd: each updated result is the gcd of the running total and the new input. Must be initialised to: 0. Here's another number theorist's perspective. I think of the gcd(X) as a canonical generator for the ideal generated by X, when defined. The ideal generated by a set X is the smallest ideal that contains it. In case X is the empty set, that ideal is the 0 ideal (not the unit ideal). -- William -- William Stein Professor of Mathematics University of Washington http://wstein.org -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
On Wed, 22 Oct 2014, Nathann Cohen wrote: given a Poset, how can you detect if this poset is a meet semilattice ? For sure we need a function for that ! And it seems that this function is exactly what join_matrix does. Of course one can try to build a [semi]lattice and see if it works or not. But is there some faster way? For a distributive lattice there is, see http://www.lirmm.fr/~nourine/Papiers/dist-recognition.ps . It links to http://download.springer.com/static/pdf/172/chp%253A10.1007%252F3-540-10854-8_14.pdf?auth66=1414046623_37fe0879bd09fb6dd923acdc2237f214ext=.pdf which says that detecting if a poset is lattice can be done on O(n^2.5). My way of doing that (what would yours be?) to: 1) Have a FinitePoset.is_meet_semilattice() function that would try to build that matrix and answer yes/no accordingly. The matrix, when built, would be cached somewhere. 2) Move Poset.join_matrix() to FiniteMeetSemiLattice The good thing is that if you: a) Build a Poset b) Notice it is a MeetSemiLattice by calling .is_meet_semilattice (which builds the matrix) c) Build the MeetSemiLattice from the poset Then step c should not re-build the matrix as the matrix is currently a lazy attribute of the hasse diagram, which has no reason to be changed by those commands. Yes. This way user can say somewhat more naturally if P.is_lattice(): LatticePoset(P).do_something() and not try: L=LatticePoset(P)... except... 2) Would it be useful to have join() function taking more than two arguments? And if so, should then also L.join(x) return x if x in L, and maybe even L.join() return L.top()? Or could join take a list as argument, so that both L.join(x,y) and L.join([x,y]) would work and latter one be possible to extend to L.join([x,y,z,...])? +1 Ok. To have join(a,b,c,...) or join([a,b,c,...])? -- Jori Mäntysalo -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
Hello ! which says that detecting if a poset is lattice can be done on O(n^2.5). Oh. Cool. Ok. To have join(a,b,c,...) or join([a,b,c,...])? Hmmm.. Well, we can have both at the same time. Something like that should do the trick: def join(elements, *args): if args: args.append(elements) elements=args elif elements in self: elements=[elements] 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
On Thu, 23 Oct 2014, Nathann Cohen wrote: which says that detecting if a poset is lattice can be done on O(n^2.5). Oh. Cool. Now somebody should just read, understand and implement it. :=) Ok. To have join(a,b,c,...) or join([a,b,c,...])? Hmmm.. Well, we can have both at the same time. True, but is it good for user perspective to have two ways to same end? -- Jori Mäntysalo -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
Hello ! True, but is it good for user perspective to have two ways to same end? When there is no risk of confusion I do not think that it is bad. Here the only risk of confusion is the following: P.join( ( (1,2), (3,4) ) ) In a poset that contains elements named (1,2), (3,4), as well as ((1,2),(3,4)). Not that there is no problem if the user types P.join( [ (1,2), (3,4) ] ) instead. It really is not a problem either to only have this P.join(a_list) available 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
On Thu, 23 Oct 2014, Nathann Cohen wrote: It really is not a problem either to only have this P.join(a_list) available And it can always be later expanded to accept also another kind of args. Btw, I noticed that there kind of is a function for this already: sum(). But not that easy to use. L=Posets.BooleanLattice(4) L=LatticePoset(L, facade=False) print sum([L(1), L(2), L(4)], L.bottom()) (Grr, facade-argument available for some but not all example posets.) -- Jori Mäntysalo -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
On Thu, 23 Oct 2014 10:38:53 +0200 Nathann Cohen nathann.co...@gmail.com wrote: Ok. To have join(a,b,c,...) or join([a,b,c,...])? Hmmm.. Well, we can have both at the same time. Something like that should do the trick: def join(elements, *args): if args: args.append(elements) elements=args elif elements in self: elements=[elements] I would personally prefer the following over the above: def foo(*args): if len(args) == 1: elements = args[0] else: elements = args ... do stuff with elements ... This way you can see which case will be used by just looking at the number of arguments and without arguing about the contents of your variables. Also join above would throw an exception when a list or other unhashable iterable is used as the only argument: sage: P = Poset() sage: [1,2] in P TypeError: unhashable type: 'list' Also, suppose that I build a poset with elements zero = (), one = (zero,), and two = (zero,one). Then join([zero,one]) and join((zero,one)) would be different, namely with elements=[zero,one] and elements=[two], even though as iterables [one,two] and (one,two) are the same. Regards, Erik Massop -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
I would personally prefer the following over the above: def foo(*args): if len(args) == 1: elements = args[0] else: elements = args ... do stuff with elements ... You should test if args in self first. If your poset contains an element named E=(x,y) and you want to compute join( E ) (which should return E) then you raise an exception. 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
Am Donnerstag, 23. Oktober 2014 11:11:34 UTC+2 schrieb Jori Mantysalo: On Thu, 23 Oct 2014, Nathann Cohen wrote: Ok. To have join(a,b,c,...) or join([a,b,c,...])? Hmmm.. Well, we can have both at the same time. True, but is it good for user perspective to have two ways to same end? this reminds me of the discussion about Permutation((1,2,3)) and Permutation([2,3,1]). Of course, the situation is a bit different there, but my feeling is that it's usually better to have only one syntax. Martin -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
this reminds me of the discussion about Permutation((1,2,3)) and Permutation([2,3,1]). Of course, the situation is a bit different there, but my feeling is that it's usually better to have only one syntax. Precisely, though the risk of misunderstanding is slightly reduced. 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. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
On Thu, 23 Oct 2014 13:06:00 +0200
Nathann Cohen nathann.co...@gmail.com wrote:
I would personally prefer the following over the above:
def foo(*args):
if len(args) == 1:
elements = args[0]
else:
elements = args
... do stuff with elements ...
You should test if args in self first. If your poset contains an
element named E=(x,y) and you want to compute join( E ) (which should
return E) then you raise an exception.
I disagree.
If you want to obtain the join of a single element E, you can use
foo([E]), foo((E,)), or foo({E}), or any iterable that contains just E.
This works even if such an iterable is an element of the poset.
Anyway, the join of a single element is not very useful (since it is the
element itself). Hence using the one-argument version of the function
for iterables seems quite innocent an abuse to me.
Without args in self things are just simpler. If you give one
argument, you know that it will be interpreted as an iterable of
elements. If you give some other number of arguments, you know that
these arguments will be interpreted as elements. You don't need to
know anything about the actual elements of the poset to figure out what
what will happen.
Finally there is a bug when you add args in self: Suppose that have
added args in self and called the new function foo'. Suppose
furthermore that you have a (facade) poset with elements x, y, and
E=(x,y). Now foo'(x,y) has args==(x,y)==E and therefore returns E
regardless of the order in the poset, which is not what is wanted from
foo'(x,y).
Regards,
Erik Massop
--
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.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Poset/lattice, join and join_matrix
Yo !
You should test if args in self first. If your poset contains an
element named E=(x,y) and you want to compute join( E ) (which should
return E) then you raise an exception.
I disagree.
If you want to obtain the join of a single element E, you can use
foo([E]), foo((E,)), or foo({E}), or any iterable that contains just E.
This works even if such an iterable is an element of the poset.
To be honest I do not care much about the join(a,b,c) syntax. Jori asked
about that, and he also wanted the function to work with empty lists,
one-element lists, and arbitrarily long lists.
I believe that supporting empty sets and sets of cardinality 1 has its
value. If supporting both join([a,b,c]) and join(a,b,c) is going to start
another war, no problem for me -- let's only support join([a,b,c])
I would be glad to see the same kind of fighting spirit when we talk of
Permutation:
sage: Permutation((1,2,3))(1)
2
sage: Permutation([1,2,3])(1)
1
That's way more dangerous than the slight inconsistency that could happen
(only when using join(a,b,c) *and not join([a,b,c])*) on some poset with
very specific elements.
Without args in self things are just simpler. If you give one
argument, you know that it will be interpreted as an iterable of
elements. If you give some other number of arguments, you know that
these arguments will be interpreted as elements.
Hmmm... There I really believe that the syntax with a set of size 1 should
be allowed. This is exactly what gcd does, and its role is precisely to
compute the join of elements in a specific poset:
sage: gcd([5])
5
sage: gcd([5,7])
1
It may be useful if some applications I guess. And join([]), too.
Finally there is a bug when you add args in self: Suppose that have
added args in self and called the new function foo'. Suppose
furthermore that you have a (facade) poset with elements x, y, and
E=(x,y). Now foo'(x,y) has args==(x,y)==E and therefore returns E
regardless of the order in the poset, which is not what is wanted from
foo'(x,y).
Indeed, indeed, this is where the possible inconsistency is. If you think
that is a problem let's only keep join([]).
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.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Poset/lattice, join and join_matrix
Yo ! 1) Why is join() defined for join-semilattices, but join_matrix() defined for posets? (I.e. it works by giving exception if the poset is not join-semilattice.) H... 1) I do not know why it is made like that, and I do not like the design 2) After several cycles of a) answer question b) think c) erase the answer, I have a question: given a Poset, how can you detect if this poset is a meet semilattice ? For sure we need a function for that ! And it seems that this function is exactly what join_matrix does. Then, how should it be implemented ? My way of doing that (what would yours be?) to: 1) Have a FinitePoset.is_meet_semilattice() function that would try to build that matrix and answer yes/no accordingly. The matrix, when built, would be cached somewhere. 2) Move Poset.join_matrix() to FiniteMeetSemiLattice The good thing is that if you: a) Build a Poset b) Notice it is a MeetSemiLattice by calling .is_meet_semilattice (which builds the matrix) c) Build the MeetSemiLattice from the poset Then step c should not re-build the matrix as the matrix is currently a lazy attribute of the hasse diagram, which has no reason to be changed by those commands. 2) Would it be useful to have join() function taking more than two arguments? And if so, should then also L.join(x) return x if x in L, and maybe even L.join() return L.top()? Or could join take a list as argument, so that both L.join(x,y) and L.join([x,y]) would work and latter one be possible to extend to L.join([x,y,z,...])? +1 3) s/join/meet for questions 1 and 2. That does not make any sense. You might want to try s/join/meet/g. 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. For more options, visit https://groups.google.com/d/optout.
