Partition options and cleanup partitions documentation

[tscrim]

Adding a Partitions.global_options() method which (globally) sets options for partitions as noted in #5439 - http://wiki.sagemath.org/combinat/Weirdness similar to PermutationOptions(). This will also affect tableau classes and friends. Additionally this will also clean up some of the documentation/code in the respective files.

---

Here's what is included in the patch:

• Added partition and tableau options
• Converted Partition_class to Partition
• Converted Partitions* (except PartitionsRestricted) into the category framework
• Converted IntegerListsLex into the category framework with element class of ClonableArray
• Renamed *katabolism to *catabolism
• Moved construction functions for partitions from_* to Partitions().from_*.
• Renamed dominate() to dominated_partitions() in Partition.

---

Apply attachment: trac_13605-partition_options-ts.patch

Depends on #14065
Depends on #6495
Depends on #14063
Depends on #13688
Depends on #14138

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: partition, options, output, days45

Author: Travis Scrimshaw

Reviewer: Andrew Mathas, Nicolas M. Thiéry

Merged: sage-5.8.beta3

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

[nthiery]

comment:1

Thanks for opening this ticket, and even better working on it :-)

For the syntax, I would prefer something like:

   Partitions.options(...)

in order to not polute the global namespace. It's relatively consistent with what's done in a couple other places (e.g. CombinatorialFreeModule). Of course, PermutationOptions should be renamed to Permutations.options as well (and by the way the l2r option of PermutationOptions should be deprecated because global options should not change the semantic).

Some places use set_options; options is more Pythonic; it makes it explicit that the same gadget can be used to set and get the options.

Cheers,
Nicolas

[AndrewMathas]

comment:2

Hi Travis,

I like the concept of various methods being controlled by global options, however, I think that it would be much better if all of the methods provided by the options were also accessible directly as methods to the class.

In fact, for me this is vital. The reason I introduced the compact option to _repr_ for partitions, tableaux and their tupled variants is that I need this option in order to improve the readability of the output from some external code that I have for working inside the graded Specht modules of arbitrary level (to be made publicly available in sage some time next year).

Consider the following:

sage: S=GradedSpechtModule(3,[4,4,3,2,1]); S
Graded Specht module S(4^2,3,2,1) with e=3 over the Integer Ring
sage: S.an_element()
  2*[1,6,10,13/2,7,11,14/3,8,12/4,9/5] 
+ 2*[1,5,10,13/2,7,11,14/3,8,12/4,9/6] 
+ 3*[1,4,10,13/2,7,11,14/3,8,12/5,9/6]
sage: S.an_element().homogeneous_components()
{0: 2*[1,5,10,13/2,7,11,14/3,8,12/4,9/6], 
 1: 2*[1,6,10,13/2,7,11,14/3,8,12/4,9/5], 
-1: 3*[1,4,10,13/2,7,11,14/3,8,12/5,9/6]}
sage: S.an_element().y(3)                    
-3*[1,3,10,13/2,7,11,14/4,8,12/5,9/6]

The elements of this Specht module are indexed, as usual, by standard tableaux which are compactly printed here inbetween brackets [...]. Without the compact=True option which is passed the _repr_ methods the output here would be almost unreadable. (It's still not that easy in this example, but compare with the output of the default _repr_ methods!:)

The way your partition options code is currently written many of the individual options are coded "inline" inside the optionable methods. This means that the only way for external code to access the different variants of an optionable method is to artificially tweak partition_options, whilst making sure to reset it to its original state after the external code has finished doing whatever it was doing.

It would be more useful, I think, if each optionable variant was directly accessible and accessible in a systematic way. This would allow external code, which might have its own options, to easily access the different variants of the method. Perhaps the best way of doing this would be something like the following:

def _repr_(self):
    try:
        repr=getattr(self, '_repr_'+ self.parent().options['display'])
    except AttributeError:
        raise ValueError, "Invalid display option"
    return repr()

def _repr_list(self):
    return '[%s]' % ', '.join('%s'%m for m in self)

def _repr_exp(self):
    exp = self.to_exp()
    return '%s' % ', '.join('%s%s' % (m+1, '' if e==1 else '^%s'%e)
                                     for (m,e) in enumerate(exp) if e > 0)

def _repr_diagram(self):
    return self.ferrers_diagram()

def _repr_compact(self):
    exp=self.to_exp()[::-1]  # reversed list of exponents
    M=max(self)
    return '%s' % ','.join('%s%s' % (M-m, '' if e==1 else '^%s'%e)
                                     for (m,e) in enumerate(exp) if e>0)

This model has the advantage of being easy to read and very easy to extend: you simply add another _repr_X method and you are done. A better approach might be to write a generic optionable_method function and then simply define

def _repr_(self):
    '''
    It's probably essential to give documentation describing 
    possible global options.
    '''
    return optionable_method(self, '_repr_', option_name='display')

where option_name defaults to name of the method but which we want to override in this case. (Perhaps it is subjective that this is better?) This would allow global options to be used uniformly across all classes. If necessary, passing arguments to the optionable methods would be straightforward too.

As a final note, can there please be an honest compact variant of _repr_ which returns a string with no spaces and is as short as possible but still readable? I want this for use inside code like the above which uses partitions to index objects. Of course, such code could do this itself but it seems more sensible to have this done inside Partition_class. I have several different examples/contexts where I want to do this and presumably other people will too?

Cheers,

Andrew

ps I am happy to help in getting all of this to work if you think these ideas are reasonable

[tscrim]

comment:3

I will separate them out into separate functions. This is probably a cleaner/more flexable way of doing things (and I believe the extra function call is relatively small compared to the actual cost of printing). I will also add a compact option to the display output options with no spaces.

Best,

Travis

[AndrewMathas]

comment:4

Thanks Travis!

I was thinking that the extra overhead wouldn't be significant, however, I was thinking of methods like _repr_. If this is adopted as a general framework then for methods like_cmp_ the overhead will probably be too high. To get around this it would be better to take the option parsing out of the individual methods and instead do it only once when the options are changed.

I am really thinking of a general options framework for parent/element classes here. In the parents, there would be a generic method which looks something like this:

def options(self, *option, **options):
    # print the current settings for the options in ``option``
    for opt in option:  
        try:
            print getattr(self.element_class,opt).__name__
        except AttributeError:
            raise ValueError, '%s is not a valid option' % opt
    # change the option settings for the options in ``options``  
    for opt in options:
        new_opt=option+'_'+options[opt]
        if hasattr(self.element_class,new_opt):
            self.element_class.__setattr__(opt, new_opt)
        else:
            raise ValueError, '%s is not a valid option for %s' % (options[opt], opt)

and, in the element classes, the different options would be coded something like this:

def _repr__list(self):
    return '[%s]' % ', '.join('%s'%m for m in self)

def _repr__exp(self):
    exp = self.to_exp()
    return '%s' % ', '.join('%s%s' % (m+1, '' if e==1 else '^%s'%e)
                                     for (m,e) in enumerate(exp) if e > 0)

def _repr__diagram(self):
    return self.ferrers_diagram()

_repr_= _repr__list  # default option for _repr_

Why don't I try and implement this and see how it works for a few different examples? Perhaps it's safer to discuss this first on sage-combinat. What do you think?

[tscrim]

comment:5

I like the concept, however how would you change the option function on those elements which have already been created? I currently don't see a way to make this feasible. This probably would be best discussed on sage-combinat-devel.

Best,

Travis

[tscrim]

Changed dependencies from #13072 to #13074

[tscrim]

comment:6

This will also incorporate TableauTuples.

[zabrocki]

comment:7

I meant Partitions(NonNegativeIntegers(), max_part=k). Sorry for the double typos (corrected in comment).

[tscrim]

Changed dependencies from #13074 to #13074 #13762

[tscrim]

comment:8

This will be based on #13762.

[tscrim]

Changed dependencies from #13074 #13762 to #13074 #13762 #13840

[tscrim]

comment:9

Almost ready for review.

[AndrewMathas]

Reviewer: Andew Mathas

[tscrim]

comment:11

For the record, the large size of this patch is due to changes in doctests in symmetric functions because the terms were reorderd.

If #10193 is not finished soon, I can commute this patch past.

[tscrim]

Changed dependencies from #13074 #13762 #13840 to #13074 #13762 #13840 #10193

[AndrewMathas]

comment:12

Hi Travis,

Could you please tell what the rationale is for having partition_options and tableau_options defined in their own files. In the long term, we need to be careful about "polluting" the file space so I don't think it is a good idea to have these little code snippets in their own files.

Similarly, I'm not convinced that it is a good idea to give the partition options their own page/index entry in the manual (btw, tableau_options doesn't seem to have a manual entry yet). I think that it would be better to have the partition options discussed in a new section at the top of partitions.rst.

Andrew

[AndrewMathas]

comment:13

Hi Travis,

Here are some more questions/issues. Consider

sage: a=Partitions(4)
sage: b=Partitions(4,order='containment')
sage: a
Partitions of the integer 4
sage: b
Partitions of the integer 4
sage: a == b
False

This is correct, of course, but it is potentially confusing because a and b look exactly the same when printed, I think that it would be better if the ordering ordering on the class was returned by _repr_, at least when the default ordering is not being used. That is, I am suggesting the following behaviour:

sage: a=Partitions(4)
sage: b=Partitions(4,order='containment')
sage: a
Partitions of the integer 4
sage: b
Partitions of the integer 4 with the containment ordering
sage: a == b
False

Continuing this example:

sage: a[:]       
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
sage: a._list.sort(); a[:]
[[1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]]

This, to me, just looks wrong: the default ordering should correspond to the order in which the partitions are generated by the iterator. That is, the default really should be 'rev_lex' or the iterator should change.

A second related issue is that in calling Partitions(4)[:], via a[:], we have created the list of all partitions of 4 BUT b does not know about this:

sage: a._list
[[1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]]
sage: b._list
Traceback (most recent call last)
...
AttributeError: 'Partitions_n_with_category' object has no attribute '_list'

In this particular example this is not important because generating the list of partitions of 4 is very quick, but if instead we were looking at the partitions of 50 or 100 then this starts to become an issue.

The reason, of course, is that Partitions is a subclass of UniqueRepresentation and order is an argument to the __init__ method of the class. I think that it would be preferable to make the "ordered classes" proper subclasses of the Partitions class with the default ordering. This way they would all be able to share their _list attributes so that the list of all partitions in the class would only ever need to be computed once. This could easily be done inside Partitions.classcall_private.

Another possibility would be to make order a part of partition_options. In terms of the code this would be almost trivial as currently order is used only inside the comparison methods. Mathematically, I think that you can argue both ways: it is useful to be able to use different orderings on the set of partitions so you don't want an individual partition to be restricted to using a fixed order, on the other the the poset of partitions with a particular order is a useful structure.

I think that Nicolas objected to doing it this way on the basis that it might break code which implicitly assumed a particular order on the partitions. I don't like this argument as it encourages bad coding: if a particular ordering is required by the code then this should be explicit in the code. (Up until now it hasn't been possible to easily change the ordering being used, but now that it is becoming possible the algorithms which require a particular ordering should be updated to make this explicit.)

I think that moving order into partition_options is the best solution.

On the other hand, if you think it better to have honestly different classes for each ordering then I think that the iterator should be modified to produce the partitions in the correct order. This would be annoying to do properly but could be done by first constructing the list of all partitions and then sorting. This is potentially time consuming, but if some one honestly needs a class for the poset with a particular order then they probably need all of its elements(?).

Andrew

[AndrewMathas]

comment:14

Short version: by making the order option part of the definition of the element and parent classes for partitions you loose the benefits of caching for partitions and for Partitions._list. Is this worth it? I am not sure that I see the benefit especially as, in practice, the order "option" is processed in the code in exactly the same way as the "real" options.

[tscrim]

comment:15

Hey Andrew,

Sorry for the delay. I'm in Burma right now and while I can generally get stable internet, some things work better than others.

Replying to @AndrewAtLarge:

Could you please tell what the rationale is for having partition_options and tableau_options defined in their own files. In the long term, we need to be careful about "polluting" the file space so I don't think it is a good idea to have these little code snippets in their own files.

Similarly, I'm not convinced that it is a good idea to give the partition options their own page/index entry in the manual (btw, tableau_options doesn't seem to have a manual entry yet). I think that it would be better to have the partition options discussed in a new section at the top of partitions.rst.

My main thought was because it is not something strictly related to partitions, but partition like objects (partition tuples and rigged configurations, there might be others). Also because partition.py is so long as is. Perhaps we could combine partition and tableau options in one file partition_tableau_options.py and one manual page. I'm in favor of having a separate manual page since it is about the display rather than the functionality, although it probably should be flushed out more with more examples and discussion.

Replying to @AndrewAtLarge:

Hi Travis,

Here are some more questions/issues. Consider

sage: a=Partitions(4)
sage: b=Partitions(4,order='containment')
sage: a
Partitions of the integer 4
sage: b
Partitions of the integer 4
sage: a == b
False

This is correct, of course, but it is potentially confusing because a and b look exactly the same when printed, I think that it would be better if the ordering ordering on the class was returned by _repr_, at least when the default ordering is not being used. That is, I am suggesting the following behaviour:

sage: a=Partitions(4)
sage: b=Partitions(4,order='containment')
sage: a
Partitions of the integer 4
sage: b
Partitions of the integer 4 with the containment ordering
sage: a == b
False

Agreed. I think this is done in a few other places too.

Continuing this example:

sage: a[:]       
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
sage: a._list.sort(); a[:]
[[1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]]

This, to me, just looks wrong: the default ordering should correspond to the order in which the partitions are generated by the iterator. That is, the default really should be 'rev_lex' or the iterator should change.

This smells like a bug since I would think sort() would used the ordering on the objects (i.e. the list may not be actual partitions but lists). However there is an small issue with the validity of the test because not all orderings on partitions are total (linear) for a fixed n. Maybe because of this, the entire idea of overriding the default ordering is a white whale.

(Although this might also be why their doesn't seem to be a good ordering in the symmetric functions (if that is, oh-joy-of-joys, I have to change a lot of doctests again).)

A second related issue is that in calling Partitions(4)[:], via a[:], we have created the list of all partitions of 4 BUT b does not know about this:

sage: a._list
[[1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]]
sage: b._list
Traceback (most recent call last)
...
AttributeError: 'Partitions_n_with_category' object has no attribute '_list'

In this particular example this is not important because generating the list of partitions of 4 is very quick, but if instead we were looking at the partitions of 50 or 100 then this starts to become an issue.

The reason, of course, is that Partitions is a subclass of UniqueRepresentation and order is an argument to the __init__ method of the class. I think that it would be preferable to make the "ordered classes" proper subclasses of the Partitions class with the default ordering. This way they would all be able to share their _list attributes so that the list of all partitions in the class would only ever need to be computed once. This could easily be done inside Partitions.__classcall_private__.

I don't think direct subclasses will work since I don't see how the data be actually communicated (without breaking into U.R.'s cache). Unless you mean they are to act like proxy classes and have a link back to the common data (which I believe would only consist of the list of partitions)?

Actually, this discussion is somewhat of a red herring since we need a second list of all of the partitions because their parent would have changed. The actual generation of the partitions I believe is amortized O(1), so at large scale, I would think other factors would start to dominate the run time (ex. the memory allocation and manipulation, but I could [easily] be wrong about this). Granted we can take advantage of the fact that the partitions are suppose to be immutable, so we can share the lists (I forget if I do this, but if I don't, I'll covert the internal data to a tuple).

For example, suppose we had shared data, then we'd have the following behavior:

sage: P = Partitions(50)
sage: Q = Partitions(50, order="dominance")
sage: Q._list[0].parent() == Q # The list would be generated with Q as the parent since it is called from Q
True
sage: P._list[0].parent() == Q
True

Another possibility would be to make order a part of partition_options. In terms of the code this would be almost trivial as currently order is used only inside the comparison methods. Mathematically, I think that you can argue both ways: it is useful to be able to use different orderings on the set of partitions so you don't want an individual partition to be restricted to using a fixed order, on the other the the poset of partitions with a particular order is a useful structure.

I think that Nicolas objected to doing it this way on the basis that it might break code which implicitly assumed a particular order on the partitions. I don't like this argument as it encourages bad coding: if a particular ordering is required by the code then this should be explicit in the code. (Up until now it hasn't been possible to easily change the ordering being used, but now that it is becoming possible the algorithms which require a particular ordering should be updated to make this explicit.)

For example, every time you do 5 > 3, you're assuming a particular order on the integers. This is very similar to the issues with facade Posets that were discussed about around 2 months (?) ago or so. Plus there are some other subtleties that can arise (I can't recall them at the moment, but I recall them having to do stored sage sessions).

I think that moving order into partition_options is the best solution.

On the other hand, if you think it better to have honestly different classes for each ordering then I think that the iterator should be modified to produce the partitions in the correct order. This would be annoying to do properly but could be done by first constructing the list of all partitions and then sorting. This is potentially time consuming, but if some one honestly needs a class for the poset with a particular order then they probably need all of its elements(?).

I strongly don't think having a subclass with the desired order is a good idea. Way too much maintenance and the problems above would likely still exist. That's all the time I have right now to reply with. Again, thank you for reviewing this!

Best,

Travis

[simon-king-jena]

comment:16

#12313 introduces a speed regression related with the fact that currently Partitions are not unique parents. This is dealt with at #13991.

If I understand correctly, you intend to make partitions unique parents. Hence, it would probably solve the speed regression. But how soon do you expect this ticket to be ready for being merged (given that one dependency does not have a positive review yet)?

At #13991, I have attached a patch that turns Partitions_FOO for various values of FOO into a UniqueRepresentation (actually, I do it for all classes which do not take lists as input data). It is not finalised yet, but since it does fix the speed regression, it could be a short-term solution, if you need more time with the ticket here.

[tscrim]

comment:17

Hey Simon,

Replying to @simon-king-jena:

#12313 introduces a speed regression related with the fact that currently Partitions are not unique parents. This is dealt with at #13991.

If I understand correctly, you intend to make partitions unique parents. Hence, it would probably solve the speed regression. But how soon do you expect this ticket to be ready for being merged (given that one dependency does not have a positive review yet)?

As soon as possible. I might move this past the #10193 dependency since it is more of a semantic rather than a functional dependency.

At #13991, I have attached a patch that turns Partitions_FOO for various values of FOO into a UniqueRepresentation (actually, I do it for all classes which do not take lists as input data). It is not finalised yet, but since it does fix the speed regression, it could be a short-term solution, if you need more time with the ticket here.

---

Hey Andrew,

As I recall, Nicolas' main reason was suppose you did something like the following:

sage: P = Partitions(4)
sage: Partitions.options(order="dominance")
sage: y = Partition([2,1])
sage: L = [x for x in P if x < y]

and you depended on this being dominance ordering. Somewhere along the way, you set the ordering back to "lex", and then needed to recreate L. You would (generally) end up with a different list. I do agree with you that (new) code relying on a particular ordering should call that order method directly, but I agree with Nicolas assessment more in that this is somewhat subtle behavior and can lead to subtle bugs.

End of the day, I'm really starting to think that deciding an ordering is more trouble than it's worth. At the very least, given #13991, should we separate this feature out to another ticket?

Last thing for now, are there any other major issues currently with this patch? I really appreciate you reviewing this.

Thank you,
Travis

Edit/PS - I'm back in the US.

[nthiery]

Changed reviewer from Andrew Mathas, Nicolas Thiery to Andrew Mathas, Nicolas M. Thiéry

[nexttime]

comment:53

Minor remark:

In combinat/sf/k_dual.py, line 42, Partition now gets imported twice (a search & replace accident I guess):

diff --git a/sage/combinat/sf/k_dual.py b/sage/combinat/sf/k_dual.py
--- a/sage/combinat/sf/k_dual.py
+++ b/sage/combinat/sf/k_dual.py
@@ -39,7 +39,7 @@ from sage.misc.cachefunc import cached_m
 from sage.categories.magmas import Magmas
 from sage.misc.constant_function import ConstantFunction
 from sage.categories.graded_hopf_algebras_with_basis import GradedHopfAlgebrasWithBasis
-from sage.combinat.partition import Partition, Partitions, Partition_class
+from sage.combinat.partition import Partition, Partitions, Partition
 from sage.rings.all import Integer
 from sage.combinat.combinat import InfiniteAbstractCombinatorialClass
 import sage.combinat.sf.sfa as sfa

(But AFAICS this is the only instance of a redundant import of it, at least regarding the patch.)

[jdemeyer]

Merged: sage-5.8.beta3

[novoselt]

comment:55

Framework for global options is awesome, although I want to complain that it was hidden in a big patch instead of being a clear little ticket...

Anyway, why "values of all options are forced to be in lower case"?

[tscrim]

comment:56

For standardness, ex. so "English" would be interpreted the same as "english" and the user wouldn't have to care about capitalization. There's a followup patch #14248 which gives the option to be case-strict or enforce only upper or lower.

[AndrewMathas]

comment:57

Replying to @novoselt:

Anyway, why "values of all options are forced to be in lower case"?

This is addressed in Travis' patch #14248.