Implement some new features for partitions (hook_cells, etc.)

[45308b42-a6d8-4b21-9ff1-54243cf32c68]

Implements the following methods for partitions:

1. A method which returns the list of cells in the hook of (i,j).
2. A method which returns the list of cells in the rim hook of (i,j).
3. A method which returns the partition removing the rim hook of (i,j).
4. A method which returns the list of cells with content k.

CC: @sagetrac-sage-combinat @anneschilling

Component: combinatorics

Keywords: partitions, sd40

Author: NUMATA, Yasuhide

Reviewer: Andrew Mathas

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

[45308b42-a6d8-4b21-9ff1-54243cf32c68]

Attachment: trac_13235-hook_cells_for_parition-nu.patch.gz

[45308b42-a6d8-4b21-9ff1-54243cf32c68]

Description changed:

--- 
+++ 
@@ -2,4 +2,5 @@
 1. A method which returns the list of cells in the hook of (i,j).
 2. A method which returns the list of cells in the rim hook of (i,j).
 3. A method which returns the partition removing the rim hook of (i,j).
+4. A method which returns the list of cells with content k.

[45308b42-a6d8-4b21-9ff1-54243cf32c68]

Changed keywords from partitions to partitions, sd40

[AndrewMathas]

Reviewer: Andrew Mathas

[AndrewMathas]

comment:3

Everything looks good although I have one comment: if the cell (i,j) is NOT contained in the diagram of the partition then all of these functions currently return an error, however, another possibility would be for the functions hook_cells and rim_hook_cells to return the empty list and remove_rim_hook to return the original partition. This is certainly compatible with the definitions. Having said this, what you have done is probably the best choice as it is likely to catch unintentional errors of people using these functions.

The following review patch makes the following minor changes.

1. Fixes the typos: "Rertuns" -> "Returns" and "The cells is not in the diagram" -> "The cell is not in the diagram"

2. Expands some of the doc strings so that they are more informative.

3. Combines the two tests 0<=k+c and k+c<=p[k] in cells_with_content() into a single statement: 0 <= k+c < p[k]. I also don't see the value in defining a new variable, p=self, so I have deleted this.

4. It replaces the remove_rim_hook() function with the list compression:

return Partition([p[r] if (r<i or p[r]<=j) else j if (r==len(p)-1 or p[r+1]<=j) else p[r+1]-1 for r in range(len(p))])

This turns out to be significantly faster:

sage: timeit( '[mu.remove_rim_hook(i,j) for mu in Partitions(10) for (i,j) in mu.cells()]' )
5 loops, best of 3: 48.4 ms per loop
sage: timeit( '[f(mu,i,j) for mu in Partitions(10) for (i,j) in mu.cells()]' )
25 loops, best of 3: 10.5 ms per loop

Here, the remove_rim_hook function is as originally defined in the patch and f is the list compression version.

A similar list compression could be used in the function rim_hook_cells() but I haven't done this.

Finally, there are some doc-test errors in partition.py but these are caused by the changes to depreciation in 5.2, so they are not caused by your patch and I have ignored them.

I have left the status as needs review as you should review my suggestions above. Once you have looked at these, and assuming make ptestlong passes, I can change this to a positive review.

[AndrewMathas]

Reivew patch (forgot to save pervious version!)

[AndrewMathas]

comment:4

Attachment: trac_13235-review-patch-am.patch.gz

Another comment: it would be good to have an analogous add_rim_hook function which returns the partition obtained by adding a rim hook of a given length and with a specified head or foot node.

[darijgr]

comment:6

What happened to this? Seems bit-rotten now. Should it be revived?

The methods seem useful.

[AndrewMathas]

comment:8

Replying to @darijgr:

What happened to this? Seems bit-rotten now. Should it be revived?

The methods seem useful.

Probably the original author lost interest. I think that methods for adding and removing rim hooks would be useful but I am not convinced about the need for the other methods. The problem is that partitions already have a huge number of methods and this makes it hard for the uninitiated to find the methods that they actually need. In addition to sage's global namespace, we probably also need to be careful that we do not over pollute the "method namespace" of the popular classes.

Of course, I have some private code that adds still more methods to the partition class and others might think that these methods are equally useless:) In this respect, it's unfortunate that python doesn't allow you to dynamically expand classes so that the user is only exposed to the "really useful" methods by default. (Actually, I have a decorator which makes this feasible, but python purists might argue against my using this in sage:)

If you want to revive this patch I'd be happy to review a working version.

Andrew