py3: some fix in set_partition

[fchapoton]

CC: @tscrim

Component: python3

Author: Frédéric Chapoton, Martin Rubey

Branch/Commit: 171f988

Reviewer: Frédéric Chapoton, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/26917

[fchapoton]

Commit: 1485eb0

[fchapoton]

New commits:

1485eb0

py3: some fix in set_partition (sortable elements only)

[fchapoton]

Branch: u/chapoton/26917

[sagetrac-git]

Changed commit from 1485eb0 to a0f038f

[sagetrac-git]

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)

[fchapoton]

comment:3

green bot, please review

[tscrim]

comment:4

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.

[fchapoton]

comment:5

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.

[mantepse]

comment:6

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.

[fchapoton]

comment:7

traceback on top of #22029:

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'>'

[tscrim]

comment:8

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].

[tscrim]

comment:9

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)

[mantepse]

comment:10

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 non-sortable ground set. Some methods may return nonsense, some methods may yield an error.

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.

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.

I am certainly not saying that we should have only set partitions on [n].

[tscrim]

comment:11

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).

[mantepse]

comment:12

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?

[jdemeyer]

comment:14

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?

[mantepse]

comment:15

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)

[tscrim]

comment:16

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 in diagram_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.

[mantepse]

comment:17

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?

[mantepse]

comment:18

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 non-totally ordered sets should go into another ticket, so I'd like to set this to positive review.

[mantepse]

Reviewer: Martin Rubey

[mantepse]

comment:20

Travis, just to be clear: feel free to set this to needs work again if you disagree with my reasoning.

[mantepse]

Changed branch from u/chapoton/26917 to u/mantepse/26917

[mantepse]

comment:22

I took the liberty of adding an example indicating the limitation.

---

New commits:

94bc96a

make clear that equality needs a totally ordered set

[mantepse]

Changed commit from a0f038f to 94bc96a

[tscrim]

comment:23

This should have been reset to needs review with the extra commit.

You should change "is not well defined" to "may give incorrect answers".

[sagetrac-git]

Changed commit from 94bc96a to 171f988

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4c0cd90	reword as requested
171f988	same for inequality

[mantepse]

Changed reviewer from Martin Rubey to none

[mantepse]

Changed author from Frédéric Chapoton to Frédéric Chapoton, Martin Rubey

[fchapoton]

Reviewer: Frédéric Chapoton

[fchapoton]

comment:26

good enough for me. Travis, do you agree ?

[tscrim]

Changed reviewer from Frédéric Chapoton to Frédéric Chapoton, Travis Scrimshaw

[tscrim]

comment:27

This is okay with me.

[embray]

comment:28

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.

[vbraun]

Changed branch from u/mantepse/26917 to 171f988