Opened 2 months ago
Closed 3 weeks ago
#26917 closed enhancement (fixed)
py3: some fix in set_partition
Reported by:  chapoton  Owned by:  

Priority:  major  Milestone:  sage8.7 
Component:  python3  Keywords:  
Cc:  tscrim  Merged in:  
Authors:  Frédéric Chapoton, Martin Rubey  Reviewers:  Frédéric Chapoton, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  171f988 (Commits)  Commit:  171f9885ff150378e69de4cdfeea2fb1d6b107ea 
Dependencies:  Stopgaps: 
Description
Change History (29)
comment:1 Changed 2 months ago by
 Branch set to u/chapoton/26917
 Commit set to 1485eb091fe76fb6968431a2c715e48a701ab7b8
 Status changed from new to needs_review
comment:2 Changed 2 months ago by
 Commit changed from 1485eb091fe76fb6968431a2c715e48a701ab7b8 to a0f038f7de5c4d6d7fad779b94735501713b49ba
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a0f038f  py3: some fix in set_partition (sortable elements only)

comment:4 Changed 2 months ago by
From the code, this should not be necessary. If this test is failing (on Py3), then is it failing because of a different order or generating an actual failure? If it is the latter, then it is definitely a bug in the code that should be fixed. If the former, then I don't understand why it is failing.
comment:5 Changed 2 months ago by
Right. Indeed, it is not failing on python3. It starts to fail (in python2) when we turn the switch in #22029.
So, it is more like that: do not mix things that cannot be sorted inside the set underlying a set partition.
comment:6 followup: ↓ 8 Changed 2 months ago by
I think there should be a decision on the assumption underlying set partitions. There are several possibilities. Currently several methods essentially assume that the ground set is totally ordered.
If we stick with this assumption, we can essentially assume that the ground set is 1,...,n. In particular, notions such as crossings and nestings make sense.
There was an effort to remove this assumption, introducing AbstractSetPartition
. I am not sure whether this is worth it, however.
comment:7 Changed 2 months ago by
traceback on top of #22029:
sage t long warnlong 54.8 src/sage/combinat/set_partition.py ********************************************************************** File "src/sage/combinat/set_partition.py", line 701, in sage.combinat.set_partition.SetPartition._latex_ Failed example: p = SetPartition([['a','c'],['b',1],[20]]) Exception raised: Traceback (most recent call last): File "/home/chapoton/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 671, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/chapoton/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 1086, in compile_and_execute exec(compiled, globs) File "<doctest sage.combinat.set_partition.SetPartition._latex_[4]>", line 1, in <module> p = SetPartition([['a','c'],['b',Integer(1)],[Integer(20)]]) File "sage/misc/classcall_metaclass.pyx", line 330, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1701) return cls.classcall(cls, *args, **kwds) File "/home/chapoton/sage/local/lib/python2.7/sitepackages/sage/combinat/set_partition.py", line 537, in __classcall_private__ return P.element_class(P, parts, check=check) File "sage/misc/classcall_metaclass.pyx", line 333, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1726) return (<PyTypeObject*>type).tp_call(cls, args, kwds) File "/home/chapoton/sage/local/lib/python2.7/sitepackages/sage/combinat/set_partition.py", line 556, in __init__ ClonableArray.__init__(self, parent, sorted(map(frozenset, s), key=min), check=check) File "sage/rings/integer.pyx", line 952, in sage.rings.integer.Integer.__richcmp__ (build/cythonized/sage/rings/integer.c:7787) return coercion_model.richcmp(left, right, op) File "sage/structure/coerce.pyx", line 1992, in sage.structure.coerce.CoercionModel_cache_maps.richcmp (build/cythonized/sage/structure/coerce.c:20111) raise bin_op_exception('>', x, y) TypeError: unsupported operand parent(s) for >: 'Integer Ring' and '<type 'str'>'
comment:8 in reply to: ↑ 6 Changed 8 weeks ago by
Replying to mantepse:
I think there should be a decision on the assumption underlying set partitions. There are several possibilities. Currently several methods essentially assume that the ground set is totally ordered.
If we stick with this assumption, we can essentially assume that the ground set is 1,...,n. In particular, notions such as crossings and nestings make sense.
There was an effort to remove this assumption, introducing
AbstractSetPartition
. I am not sure whether this is worth it, however.
I think we should keep the current implementation: Let the methods error out when the SetPartition
is not on [n]
. For permutations, this makes more sense to have a special class for "standard" permutations (speed and the essentially ubiquity of {1,...,n}
). However, this creates a fair bit of extra maintenance burden.
TL;DR I think we should avoid forcing the ground set to be [n]
.
comment:9 followup: ↓ 14 Changed 8 weeks ago by
comment:7 is a hard error that prevents a set partition from being constructed from any incomparable objects.
My opinion would be to instead do this change:
ClonableArray.__init__(self, parent, sorted(map(frozenset, s), key=min), check=check) +try: + ClonableArray.__init__(self, parent, sorted(map(frozenset, s), key=min), check=check) +except TypeError: + ClonableArray.__init__(self, parent, sorted(map(frozenset, s), key=lambda x: str(min(x))), + check=check)
comment:10 Changed 8 weeks ago by
Hi Travis!
So, would you (just as I would) vote for removing AbstractSetPartition
again?
I admit I am confused about would you would prefer:
1) a single implementation of set partitions, with arbitrary, possibly nonsortable ground set. Some methods may return nonsense, some methods may yield an error.
2) a single implementation of set partitions, with arbitrary, possibly nonsortable ground set. Methods may yield an error, but will not return nonsense. I believe that this is hard to achieve, when we want to keep speed.
3) it seems that you (and me also) do not like the current state, which is an incomplete split between sortable and nonsortable ground set.
I am certainly not saying that we should have only set partitions on [n]
.
comment:11 Changed 8 weeks ago by
I don't like it, but there are reasons for having it for comb. Hopf algebras IIRC. At least with a partial split, we can be fluid about what goes where, which lowers the maintenance burden.
I am for option 1 as people doing things on more generic set partitions will almost certainly not be doing any other special methods (mainly, they are probably looking to enumerate the set partitions).
comment:12 followup: ↓ 16 Changed 7 weeks ago by
A related ticket is #25451. However, I think it would indeed be better to get rid of AbstractSetPartition
again. It is only used in diagram_algebras.py
.
Apart from that I would like to go with Travis' proposal. Any objections?
comment:13 Changed 7 weeks ago by
 Status changed from needs_review to needs_info
comment:14 in reply to: ↑ 9 ; followup: ↓ 15 Changed 7 weeks ago by
Replying to tscrim:
comment:7 is a hard error that prevents a set partition from being constructed from any incomparable objects.
My opinion would be to instead do this change:
ClonableArray.__init__(self, parent, sorted(map(frozenset, s), key=min), check=check) +try: + ClonableArray.__init__(self, parent, sorted(map(frozenset, s), key=min), check=check) +except TypeError: + ClonableArray.__init__(self, parent, sorted(map(frozenset, s), key=lambda x: str(min(x))), + check=check)
Is the sorting relevant in the first place? Couldn't we just keep things in the order that the user gives them?
comment:15 in reply to: ↑ 14 Changed 7 weeks ago by
Couldn't we just keep things in the order that the user gives them?
No, because we want to be able to compare two set partitions quickly.
(the real thing would be to use restricted growth words, but there was a vote against it, and so far nobody asked for really fast set partitions)
comment:16 in reply to: ↑ 12 ; followup: ↓ 17 Changed 7 weeks ago by
Replying to mantepse:
A related ticket is #25451. However, I think it would indeed be better to get rid of
AbstractSetPartition
again. It is only used indiagram_algebras.py
.Apart from that I would like to go with Travis' proposal. Any objections?
Yes, I do. This abstraction is useful for the diagram algebras. The number of uses (as long as it is more than one) is not a good reason for removal. It also is not really a big maintenance burden. So 1, still.
comment:17 in reply to: ↑ 16 Changed 7 weeks ago by
Yes, I do. This abstraction is useful for the diagram algebras. The number of uses (as long as it is more than one) is not a good reason for removal. It also is not really a big maintenance burden. So 1, still.
I don't mind. What's the second use of AbstractSetPartition
?
Can we go ahead with your proposal in this ticket?
comment:18 Changed 7 weeks ago by
I just realised that I already said that equality of set partitions cannot work
sage: n=4; s = [frozenset([2*i, 2*i+1]) for i in range(n)] sage: p1 = SetPartition([[s[0]], [s[1]]]) sage: p2 = SetPartition([[s[1]], [s[0]]]) sage: p1 == p2 False
Therefore I think that having an error raised when the base set is not totally ordered is actually much better. (I do realise that the example above won't give an error in python3, but at least we shouldn't make matters worse.)
If really desired, generalising set partitions to nontotally ordered sets should go into another ticket, so I'd like to set this to positive review.
comment:19 Changed 7 weeks ago by
 Reviewers set to Martin Rubey
 Status changed from needs_info to positive_review
comment:20 Changed 7 weeks ago by
Travis, just to be clear: feel free to set this to needs work
again if you disagree with my reasoning.
comment:21 Changed 7 weeks ago by
 Branch changed from u/chapoton/26917 to u/mantepse/26917
comment:22 Changed 7 weeks ago by
 Commit changed from a0f038f7de5c4d6d7fad779b94735501713b49ba to 94bc96a01ab26655f1ffeb96da90e07a69da59c3
I took the liberty of adding an example indicating the limitation.
New commits:
94bc96a  make clear that equality needs a totally ordered set

comment:23 Changed 7 weeks ago by
 Status changed from positive_review to needs_work
This should have been reset to needs review with the extra commit.
You should change "is not well defined" to "may give incorrect answers".
comment:24 Changed 7 weeks ago by
 Commit changed from 94bc96a01ab26655f1ffeb96da90e07a69da59c3 to 171f9885ff150378e69de4cdfeea2fb1d6b107ea
comment:25 Changed 7 weeks ago by
 Reviewers Martin Rubey deleted
 Status changed from needs_work to needs_review
comment:26 Changed 7 weeks ago by
 Reviewers set to Frédéric Chapoton
good enough for me. Travis, do you agree ?
comment:27 Changed 6 weeks ago by
 Reviewers changed from Frédéric Chapoton to Frédéric Chapoton, Travis Scrimshaw
 Status changed from needs_review to positive_review
This is okay with me.
comment:28 Changed 4 weeks ago by
 Milestone changed from sage8.6 to sage8.7
Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sagepending or sagewishlist.
comment:29 Changed 3 weeks ago by
 Branch changed from u/mantepse/26917 to 171f9885ff150378e69de4cdfeea2fb1d6b107ea
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
py3: some fix in set_partition (sortable elements only)