Improvements to SetPartitions

[tscrim]

This ticket does the following:

• Creates a class for all set partitions.
• Allows equality between different set partitions of different parents.
• Implements a total ordering on set partitions based upon ordering the parts.
• Implements a fully consistent string representation.
• Adds multiple methods, including accessing the base set for the set partition.

Apply: attachment: trac_15143-set_partitions-folded-ts.2.patch

Depends on #14234

CC: @sagetrac-sage-combinat @zabrocki

Component: combinatorics

Author: Travis Scrimshaw

Reviewer: Darij Grinberg, Mike Zabrocki

Merged: sage-5.13.beta0

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

[darijgr]

comment:2

Here is a started review. Before I continue, I'd like you to address some questions:

• Your __mul__ method gives the same result as the existing inf method, but seems to be faster at arriving there. Better to reimplement the latter as an alias for the former? If you do so, the docstrings should probably be merged.

• I don't understand the docstring of ordered_set_partition_action, nor do I understand the definition given in [LM2011] (but I have not really tried). Maybe you can improve it still? What are A_{i_1}, A_{i_2} etc.?

• I have replaced the docstring and the implementation of is_atomic to something that matches the definition of "atomic" in the context of multiplicative generators of NCSym. I hope this is what you really meant. First, the empty set partition is no longer atomic; second, [[1, 4], [2], [3]] is now atomic despite max(2) < min(3) because there is a max(1, 4) to spoil the game.

• I have removed the part about set compositions in the docstring of __mul__ because the method only appears on the SetPartition class.

• I see you have changed the parent of all set partitions to not include the base set. I am not saying this is wrong; just letting you know that I cannot fully test the consequences of this change and so my review will be somewhat incomplete even when it is finished.

[tscrim]

comment:3

Thanks for looking at this patch.

Replying to @darijgr:

Here is a started review. Before I continue, I'd like you to address some questions:

• Your __mul__ method gives the same result as the existing inf method, but seems to be faster at arriving there. Better to reimplement the latter as an alias for the former? If you do so, the docstrings should probably be merged.

I'll take a look at it (although both of these methods were prior implementations).

• I don't understand the docstring of ordered_set_partition_action, nor do I understand the definition given in [LM2011] (but I have not really tried). Maybe you can improve it still? What are A_{i_1}, A_{i_2} etc.?

I'll expand on the docstring.

• I have replaced the docstring and the implementation of is_atomic to something that matches the definition of "atomic" in the context of multiplicative generators of NCSym. I hope this is what you really meant. First, the empty set partition is no longer atomic; second, [[1, 4], [2], [3]] is now atomic despite max(2) < min(3) because there is a max(1, 4) to spoil the game.

I was worried I oversimplified it. Thanks for fixing it.

Let's see if we can close a small can of worms. Well, since 1 usually isn't considered as a generator of a unital algebra, it's okay that the empty set partition is not atomic. I'm assuming that similarly 1 is not considered a primitive of a Hopf algebra. However by the definition directly, it would be considered atomic since there is no non-trivial split, but I'll change it to state explicitly we don't consider it atomic. This is similar to how we don't consider 1 as being prime.

• I have removed the part about set compositions in the docstring of __mul__ because the method only appears on the SetPartition class.

• I see you have changed the parent of all set partitions to not include the base set. I am not saying this is wrong; just letting you know that I cannot fully test the consequences of this change and so my review will be somewhat incomplete even when it is finished.

I made sure to put in some tests for things like equality and for the is_less_than and is_strict_refinement methods when comparing objects with different parents. Doing it this way will net a (very) small speedup in creation since we don't have to find the right parent by taking the union of sets (I didn't measure). It also made me feel more secure in my implementation of NCSym.

I'll post the new version of the patch tomorrow.

[darijgr]

comment:4

Oops, I didn't realize __mul__ was there before you. Anyway, I'll take a look at it if you don't; it sounds like a cheap speedup one can get from just throwing away old code.

The Bergeron-Zabrocki paper you linked me to (thank you!) says "A is called atomic if it is non-empty and not splittable"; note the "non-empty" here. But apparently some other sources don't require non-emptiness. As far as I am concerned, the "non-empty" convention makes more sense; these are supposed to be a free monoid generating set of the monoid of all set partitions, so there is no reason the unity of the monoid should be there.

[zabrocki]

comment:6

I started testing parts of this patch and found a minor bug that the partition type isn't checked.

sage: SetPartition([[1,2],[4]]) in SetPartitions([1,2,4],[3])
True

The other parts that I did test are looking good.

[zabrocki]

comment:7

Also, I've found that SetPartition accepts the following bad input. Maybe it should raise an error.

sage: SetPartition([[1,2],[2,3]])
{{1, 2}, {2, 3}}

[darijgr]

comment:8

I understand this as a tradeoff with speed -- maybe add a check variable which is set to True by default, and go over all existing code that involves set partitions (hopefully not that much, and some of it will have to be modified anyway since #15143 breaks some doctests by changing output order) to make all calls to SetPartition call it with False?

Partition algebras are HUGE; I definitely wouldn't want to see them slowed down by input sanitizing.

[tscrim]

comment:9

Attachment: trac_15143-set_partitions-ts.patch.gz

Here's the new version with better containment checks and doctest corrects to partition algebras.

For patchbot:

Apply: trac_15143-set_partitions-ts.patch

[tscrim]

Dependencies: #14234

[darijgr]

comment:10

Thanks for the fixes. In other news, I am now sufficiently convinced of the superiority of __mul__ that I'm replacing inf by an alias to __mul__:

sage: %timeit SetPartition([[1,3],[2,6,5]]).__mul__(SetPartition([[1,2],[3],[6]]))                                               
1000 loops, best of 3: 1.61 ms per loop
sage: %timeit SetPartition([[1,3],[2,6,5]]).inf(SetPartition([[1,2],[3],[6]]))    
100 loops, best of 3: 1.96 ms per loop
sage: %timeit SetPartition([[1],[2,3]]).__mul__(SetPartition([[1,2],[3]]))        
1000 loops, best of 3: 1.3 ms per loop
sage: %timeit SetPartition([[1],[2,3]]).inf(SetPartition([[1,2],[3]]))    
1000 loops, best of 3: 1.52 ms per loop
sage: %timeit SetPartition([[1],[2],[3]]).__mul__(SetPartition([[1],[2],[3]]))
1000 loops, best of 3: 1.92 ms per loop
sage: %timeit SetPartition([[1],[2],[3]]).inf(SetPartition([[1],[2],[3]]))    
100 loops, best of 3: 2.37 ms per loop
sage: %timeit SetPartition([[1],[2],[3],[4],[5],[6],[7]]).__mul__(SetPartition([[1],[2],[4],[5],[8],[9],[3]]))
100 loops, best of 3: 5.61 ms per loop
sage: %timeit SetPartition([[1],[2],[3],[4],[5],[6],[7]]).inf(SetPartition([[1],[2],[4],[5],[8],[9],[3]]))    
100 loops, best of 3: 9.28 ms per loop
sage: %timeit SetPartition([[1,3,37]]).__mul__(SetPartition([[13,3,7]]))                                      
1000 loops, best of 3: 662 us per loop
sage: %timeit SetPartition([[1,3,37]]).inf(SetPartition([[13,3,7]]))    
1000 loops, best of 3: 744 us per loop

I think the check variable does nothing when one generates a set partition. I'd be happy if you could see if there is something gained by omitting the check, and if so, making the variable work. But I must admit you have sped up the generation of a set partition by a factor of about 2 (compared to pre-#15143) already, so the net effect is a positive one even if the check is left in.

I still don't understand the doc of ordered_set_partition_action. What is unclear to me is this:

        `A_{ \{ i_1, i_2, \ldots, i_k \} }` denote the sub-partition
        `\{A_{i_1}, A_{i_2}, \ldots, A_{i_k}\}`.

Other than this method, I'll call this review done. Unfortunately, I'm out of leeway now as far as free time is concerned, and someone else will likely have to review the NCSym patch.