#26917 closed enhancement (fixed)

py3: some fix in set_partition

Reported by: chapoton Owned by:
Priority: major Milestone: sage-8.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 12 months ago by chapoton

  • Branch set to u/chapoton/26917
  • Commit set to 1485eb091fe76fb6968431a2c715e48a701ab7b8
  • Status changed from new to needs_review

New commits:

1485eb0py3: some fix in set_partition (sortable elements only)

comment:2 Changed 12 months ago by git

  • Commit changed from 1485eb091fe76fb6968431a2c715e48a701ab7b8 to a0f038f7de5c4d6d7fad779b94735501713b49ba

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a0f038fpy3: some fix in set_partition (sortable elements only)

comment:3 Changed 12 months ago by chapoton

  • Cc tscrim added

green bot, please review

comment:4 Changed 12 months ago by tscrim

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 12 months ago by chapoton

Right. Indeed, it is not failing on python3. It starts to fail (in pyhton2) 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.

Version 0, edited 12 months ago by chapoton (next)

comment:6 follow-up: Changed 12 months ago by 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.

comment:7 Changed 12 months ago by chapoton

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

comment:8 in reply to: ↑ 6 Changed 12 months ago by tscrim

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 follow-up: Changed 12 months ago by 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)

comment:10 Changed 12 months ago by mantepse

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

comment:11 Changed 12 months ago by tscrim

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 follow-up: Changed 12 months ago by 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?

comment:13 Changed 12 months ago by mantepse

  • Status changed from needs_review to needs_info

comment:14 in reply to: ↑ 9 ; follow-up: Changed 12 months ago by jdemeyer

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 12 months ago by mantepse

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 ; follow-up: Changed 12 months ago by tscrim

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.

comment:17 in reply to: ↑ 16 Changed 12 months ago by mantepse

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 12 months ago by mantepse

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.

comment:19 Changed 12 months ago by mantepse

  • Reviewers set to Martin Rubey
  • Status changed from needs_info to positive_review

comment:20 Changed 12 months ago by mantepse

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

comment:21 Changed 12 months ago by mantepse

  • Branch changed from u/chapoton/26917 to u/mantepse/26917

comment:22 Changed 12 months ago by mantepse

  • Commit changed from a0f038f7de5c4d6d7fad779b94735501713b49ba to 94bc96a01ab26655f1ffeb96da90e07a69da59c3

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


New commits:

94bc96amake clear that equality needs a totally ordered set

comment:23 Changed 12 months ago by tscrim

  • 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 12 months ago by git

  • Commit changed from 94bc96a01ab26655f1ffeb96da90e07a69da59c3 to 171f9885ff150378e69de4cdfeea2fb1d6b107ea

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

4c0cd90reword as requested
171f988same for inequality

comment:25 Changed 12 months ago by mantepse

  • Authors changed from Frédéric Chapoton to Frédéric Chapoton, Martin Rubey
  • Reviewers Martin Rubey deleted
  • Status changed from needs_work to needs_review

comment:26 Changed 11 months ago by chapoton

  • Reviewers set to Frédéric Chapoton

good enough for me. Travis, do you agree ?

comment:27 Changed 11 months ago by tscrim

  • 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 11 months ago by embray

  • Milestone changed from sage-8.6 to sage-8.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 sage-pending or sage-wishlist.

comment:29 Changed 11 months ago by vbraun

  • Branch changed from u/mantepse/26917 to 171f9885ff150378e69de4cdfeea2fb1d6b107ea
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.