Sage: Ticket #26917: py3: some fix in set_partition
https://trac.sagemath.org/ticket/26917
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/26917
Trac 1.1.6chapotonWed, 19 Dec 2018 19:26:37 GMTstatus changed; commit, branch set
https://trac.sagemath.org/ticket/26917#comment:1
https://trac.sagemath.org/ticket/26917#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>1485eb091fe76fb6968431a2c715e48a701ab7b8</em>
</li>
<li><strong>branch</strong>
set to <em>u/chapoton/26917</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=1485eb091fe76fb6968431a2c715e48a701ab7b8"><span class="icon"></span>1485eb0</a></td><td><code>py3: some fix in set_partition (sortable elements only)</code>
</td></tr></table>
TicketgitWed, 19 Dec 2018 19:32:12 GMTcommit changed
https://trac.sagemath.org/ticket/26917#comment:2
https://trac.sagemath.org/ticket/26917#comment:2
<ul>
<li><strong>commit</strong>
changed from <em>1485eb091fe76fb6968431a2c715e48a701ab7b8</em> to <em>a0f038f7de5c4d6d7fad779b94735501713b49ba</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=a0f038f7de5c4d6d7fad779b94735501713b49ba"><span class="icon"></span>a0f038f</a></td><td><code>py3: some fix in set_partition (sortable elements only)</code>
</td></tr></table>
TicketchapotonThu, 20 Dec 2018 07:42:19 GMTcc set
https://trac.sagemath.org/ticket/26917#comment:3
https://trac.sagemath.org/ticket/26917#comment:3
<ul>
<li><strong>cc</strong>
<em>tscrim</em> added
</li>
</ul>
<p>
green bot, please review
</p>
TickettscrimThu, 20 Dec 2018 07:48:17 GMT
https://trac.sagemath.org/ticket/26917#comment:4
https://trac.sagemath.org/ticket/26917#comment:4
<p>
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.
</p>
TicketchapotonThu, 20 Dec 2018 08:34:19 GMT
https://trac.sagemath.org/ticket/26917#comment:5
https://trac.sagemath.org/ticket/26917#comment:5
<p>
Right. Indeed, it is not failing on python3. It starts to fail (in python2) when we turn the switch in <a class="closed ticket" href="https://trac.sagemath.org/ticket/22029" title="enhancement: Element richcmp: never use id() (closed: fixed)">#22029</a>.
</p>
<p>
So, it is more like that: do not mix things that cannot be sorted inside the set underlying a set partition.
</p>
TicketmantepseThu, 20 Dec 2018 08:49:11 GMT
https://trac.sagemath.org/ticket/26917#comment:6
https://trac.sagemath.org/ticket/26917#comment:6
<p>
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.
</p>
<p>
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.
</p>
<p>
There was an effort to remove this assumption, introducing <code>AbstractSetPartition</code>. I am not sure whether this is worth it, however.
</p>
TicketchapotonThu, 20 Dec 2018 17:51:37 GMT
https://trac.sagemath.org/ticket/26917#comment:7
https://trac.sagemath.org/ticket/26917#comment:7
<p>
traceback on top of <a class="closed ticket" href="https://trac.sagemath.org/ticket/22029" title="enhancement: Element richcmp: never use id() (closed: fixed)">#22029</a>:
</p>
<pre class="wiki">sage -t --long --warn-long 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/site-packages/sage/doctest/forker.py", line 671, in _run
self.compile_and_execute(example, compiler, test.globs)
File "/home/chapoton/sage/local/lib/python2.7/site-packages/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/site-packages/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/site-packages/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'>'
</pre>
TickettscrimFri, 21 Dec 2018 00:51:04 GMT
https://trac.sagemath.org/ticket/26917#comment:8
https://trac.sagemath.org/ticket/26917#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26917#comment:6" title="Comment 6">mantepse</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
<p>
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.
</p>
<p>
There was an effort to remove this assumption, introducing <code>AbstractSetPartition</code>. I am not sure whether this is worth it, however.
</p>
</blockquote>
<p>
I think we should keep the current implementation: Let the methods error out when the <code>SetPartition</code> is not on <code>[n]</code>. For permutations, this makes more sense to have a special class for "standard" permutations (speed and the essentially ubiquity of <code>{1,...,n}</code>). However, this creates a fair bit of extra maintenance burden.
</p>
<p>
TL;DR I think we should avoid forcing the ground set to be <code>[n]</code>.
</p>
TickettscrimFri, 21 Dec 2018 00:55:01 GMT
https://trac.sagemath.org/ticket/26917#comment:9
https://trac.sagemath.org/ticket/26917#comment:9
<p>
<a class="ticket" href="https://trac.sagemath.org/ticket/26917#comment:7" title="Comment 7">comment:7</a> is a hard error that prevents a set partition from being constructed from any incomparable objects.
</p>
<p>
My opinion would be to instead do this change:
</p>
<div class="wiki-code"><div class="code"><pre><span class="gd">-ClonableArray.__init__(self, parent, sorted(map(frozenset, s), key=min), check=check)
</span><span class="gi">+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)
</span></pre></div></div>
TicketmantepseFri, 21 Dec 2018 07:12:02 GMT
https://trac.sagemath.org/ticket/26917#comment:10
https://trac.sagemath.org/ticket/26917#comment:10
<p>
Hi Travis!
</p>
<p>
So, would you (just as I would) vote for removing <code>AbstractSetPartition</code> again?
</p>
<p>
I admit I am confused about would you would prefer:
</p>
<p>
1) a single implementation of set partitions, with arbitrary, possibly non-sortable ground set. Some methods may return nonsense, some methods may yield an error.
</p>
<p>
2) a single implementation of set partitions, with arbitrary, possibly non-sortable 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.
</p>
<p>
3) it seems that you (and me also) do not like the current state, which is an incomplete split between sortable and non-sortable ground set.
</p>
<p>
I am certainly not saying that we should have only set partitions on <code>[n]</code>.
</p>
TickettscrimFri, 21 Dec 2018 18:11:03 GMT
https://trac.sagemath.org/ticket/26917#comment:11
https://trac.sagemath.org/ticket/26917#comment:11
<p>
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.
</p>
<p>
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).
</p>
TicketmantepseTue, 25 Dec 2018 10:02:16 GMT
https://trac.sagemath.org/ticket/26917#comment:12
https://trac.sagemath.org/ticket/26917#comment:12
<p>
A related ticket is <a class="new ticket" href="https://trac.sagemath.org/ticket/25451" title="enhancement: move methods on general set partitions into AbstractSetPartition (new)">#25451</a>. However, I think it would indeed be better to get rid of <code>AbstractSetPartition</code> again. It is only used in <code>diagram_algebras.py</code>.
</p>
<p>
Apart from that I would like to go with Travis' proposal. Any objections?
</p>
TicketmantepseTue, 25 Dec 2018 11:03:37 GMTstatus changed
https://trac.sagemath.org/ticket/26917#comment:13
https://trac.sagemath.org/ticket/26917#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
TicketjdemeyerTue, 25 Dec 2018 13:10:58 GMT
https://trac.sagemath.org/ticket/26917#comment:14
https://trac.sagemath.org/ticket/26917#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26917#comment:9" title="Comment 9">tscrim</a>:
</p>
<blockquote class="citation">
<p>
<a class="ticket" href="https://trac.sagemath.org/ticket/26917#comment:7" title="Comment 7">comment:7</a> is a hard error that prevents a set partition from being constructed from any incomparable objects.
</p>
<p>
My opinion would be to instead do this change:
</p>
<div class="wiki-code"><div class="code"><pre><span class="gd">-ClonableArray.__init__(self, parent, sorted(map(frozenset, s), key=min), check=check)
</span><span class="gi">+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)
</span></pre></div></div></blockquote>
<p>
Is the sorting relevant in the first place? Couldn't we just keep things in the order that the user gives them?
</p>
TicketmantepseTue, 25 Dec 2018 14:50:48 GMT
https://trac.sagemath.org/ticket/26917#comment:15
https://trac.sagemath.org/ticket/26917#comment:15
<blockquote class="citation">
<p>
Couldn't we just keep things in the order that the user gives them?
</p>
</blockquote>
<p>
No, because we want to be able to compare two set partitions quickly.
</p>
<p>
(the real thing would be to use restricted growth words, but there was a vote against it, and so far nobody asked for <em>really</em> fast set partitions)
</p>
TickettscrimTue, 25 Dec 2018 15:41:15 GMT
https://trac.sagemath.org/ticket/26917#comment:16
https://trac.sagemath.org/ticket/26917#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26917#comment:12" title="Comment 12">mantepse</a>:
</p>
<blockquote class="citation">
<p>
A related ticket is <a class="new ticket" href="https://trac.sagemath.org/ticket/25451" title="enhancement: move methods on general set partitions into AbstractSetPartition (new)">#25451</a>. However, I think it would indeed be better to get rid of <code>AbstractSetPartition</code> again. It is only used in <code>diagram_algebras.py</code>.
</p>
<p>
Apart from that I would like to go with Travis' proposal. Any objections?
</p>
</blockquote>
<p>
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.
</p>
TicketmantepseTue, 25 Dec 2018 18:24:01 GMT
https://trac.sagemath.org/ticket/26917#comment:17
https://trac.sagemath.org/ticket/26917#comment:17
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
I don't mind. What's the second use of <code>AbstractSetPartition</code>?
</p>
<p>
Can we go ahead with your proposal in this ticket?
</p>
TicketmantepseWed, 26 Dec 2018 08:44:13 GMT
https://trac.sagemath.org/ticket/26917#comment:18
https://trac.sagemath.org/ticket/26917#comment:18
<p>
I just realised that I already said that equality of set partitions cannot work
</p>
<pre class="wiki">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
</pre><p>
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.)
</p>
<p>
If really desired, generalising set partitions to non-totally ordered sets should go into another ticket, so I'd like to set this to positive review.
</p>
TicketmantepseWed, 26 Dec 2018 08:44:47 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/26917#comment:19
https://trac.sagemath.org/ticket/26917#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Martin Rubey</em>
</li>
</ul>
TicketmantepseWed, 26 Dec 2018 08:45:28 GMT
https://trac.sagemath.org/ticket/26917#comment:20
https://trac.sagemath.org/ticket/26917#comment:20
<p>
Travis, just to be clear: feel free to set this to <code>needs work</code> again if you disagree with my reasoning.
</p>
TicketmantepseWed, 26 Dec 2018 09:23:01 GMTbranch changed
https://trac.sagemath.org/ticket/26917#comment:21
https://trac.sagemath.org/ticket/26917#comment:21
<ul>
<li><strong>branch</strong>
changed from <em>u/chapoton/26917</em> to <em>u/mantepse/26917</em>
</li>
</ul>
TicketmantepseWed, 26 Dec 2018 09:24:04 GMTcommit changed
https://trac.sagemath.org/ticket/26917#comment:22
https://trac.sagemath.org/ticket/26917#comment:22
<ul>
<li><strong>commit</strong>
changed from <em>a0f038f7de5c4d6d7fad779b94735501713b49ba</em> to <em>94bc96a01ab26655f1ffeb96da90e07a69da59c3</em>
</li>
</ul>
<p>
I took the liberty of adding an example indicating the limitation.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=94bc96a01ab26655f1ffeb96da90e07a69da59c3"><span class="icon"></span>94bc96a</a></td><td><code>make clear that equality needs a totally ordered set</code>
</td></tr></table>
TickettscrimWed, 26 Dec 2018 17:02:08 GMTstatus changed
https://trac.sagemath.org/ticket/26917#comment:23
https://trac.sagemath.org/ticket/26917#comment:23
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
This should have been reset to needs review with the extra commit.
</p>
<p>
You should change "is not well defined" to "may give incorrect answers".
</p>
TicketgitWed, 26 Dec 2018 17:53:46 GMTcommit changed
https://trac.sagemath.org/ticket/26917#comment:24
https://trac.sagemath.org/ticket/26917#comment:24
<ul>
<li><strong>commit</strong>
changed from <em>94bc96a01ab26655f1ffeb96da90e07a69da59c3</em> to <em>171f9885ff150378e69de4cdfeea2fb1d6b107ea</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=4c0cd90df5c839bb9edace8f2899166531bfac5b"><span class="icon"></span>4c0cd90</a></td><td><code>reword as requested</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=171f9885ff150378e69de4cdfeea2fb1d6b107ea"><span class="icon"></span>171f988</a></td><td><code>same for inequality</code>
</td></tr></table>
TicketmantepseWed, 26 Dec 2018 17:55:24 GMTstatus, author changed; reviewer deleted
https://trac.sagemath.org/ticket/26917#comment:25
https://trac.sagemath.org/ticket/26917#comment:25
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>reviewer</strong>
<em>Martin Rubey</em> deleted
</li>
<li><strong>author</strong>
changed from <em>Frédéric Chapoton</em> to <em>Frédéric Chapoton, Martin Rubey</em>
</li>
</ul>
TicketchapotonMon, 31 Dec 2018 19:50:47 GMTreviewer set
https://trac.sagemath.org/ticket/26917#comment:26
https://trac.sagemath.org/ticket/26917#comment:26
<ul>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton</em>
</li>
</ul>
<p>
good enough for me. Travis, do you agree ?
</p>
TickettscrimTue, 01 Jan 2019 17:29:44 GMTstatus, reviewer changed
https://trac.sagemath.org/ticket/26917#comment:27
https://trac.sagemath.org/ticket/26917#comment:27
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Frédéric Chapoton</em> to <em>Frédéric Chapoton, Travis Scrimshaw</em>
</li>
</ul>
<p>
This is okay with me.
</p>
TicketembrayTue, 15 Jan 2019 18:16:10 GMTmilestone changed
https://trac.sagemath.org/ticket/26917#comment:28
https://trac.sagemath.org/ticket/26917#comment:28
<ul>
<li><strong>milestone</strong>
changed from <em>sage-8.6</em> to <em>sage-8.7</em>
</li>
</ul>
<p>
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 sage-pending or sage-wishlist.
</p>
TicketvbraunWed, 23 Jan 2019 14:17:46 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/26917#comment:29
https://trac.sagemath.org/ticket/26917#comment:29
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/mantepse/26917</em> to <em>171f9885ff150378e69de4cdfeea2fb1d6b107ea</em>
</li>
</ul>
Ticket