Opened 6 years ago

Closed 6 years ago

Last modified 5 years ago

#13605 closed enhancement (fixed)

Partition options and cleanup partitions documentation

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-5.8
Component: combinatorics Keywords: partition, options, output, days45
Cc: sage-combinat Merged in: sage-5.8.beta3
Authors: Travis Scrimshaw Reviewers: Andrew Mathas, Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14065 #6495 #14063 #13688 #14138 Stopgaps:

Description (last modified by jdemeyer)

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 trac_13605-partition_options-ts.patch

Attachments (2)

trac_13605-partition_options-review-am.patch (141.3 KB) - added by andrew.mathas 6 years ago.
Review patch which primarily imporves option handling and fixes tex_from_array
trac_13605-partition_options-ts.patch (389.2 KB) - added by tscrim 6 years ago.
Minor rebase to 5.8.beta1

Download all attachments as: .zip

Change History (59)

comment:1 Changed 6 years ago by nthiery

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

comment:2 Changed 6 years ago by andrew.mathas

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

Last edited 6 years ago by andrew.mathas (previous) (diff)

comment:3 follow-up: Changed 6 years ago by tscrim

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

comment:4 in reply to: ↑ 3 Changed 6 years ago by andrew.mathas

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?

comment:5 Changed 6 years ago by tscrim

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

comment:6 Changed 6 years ago by tscrim

  • Dependencies changed from #13072 to #13074
  • Description modified (diff)

This will also incorporate TableauTuples.

comment:7 Changed 6 years ago by zabrocki

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

comment:8 Changed 6 years ago by tscrim

  • Dependencies changed from #13074 to #13074 #13762

This will be based on #13762.

comment:9 Changed 6 years ago by tscrim

  • Dependencies changed from #13074 #13762 to #13074 #13762 #13840
  • Description modified (diff)

Almost ready for review.

comment:10 Changed 6 years ago by andrew.mathas

  • Reviewers set to Andew Mathas

comment:11 Changed 6 years ago by tscrim

  • Dependencies changed from #13074 #13762 #13840 to #13074 #13762 #13840 #10193
  • Description modified (diff)
  • Status changed from new to needs_review

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.

comment:12 Changed 6 years ago by andrew.mathas

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

comment:13 follow-ups: Changed 6 years ago by andrew.mathas

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

comment:14 in reply to: ↑ 13 Changed 6 years ago by andrew.mathas

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.

comment:15 in reply to: ↑ 13 Changed 6 years ago by tscrim

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 andrew.mathas:

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 andrew.mathas:

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

comment:16 follow-up: Changed 6 years ago by SimonKing

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

comment:17 in reply to: ↑ 16 ; follow-up: Changed 6 years ago by tscrim

Hey Simon,

Replying to SimonKing:

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

Last edited 6 years ago by tscrim (previous) (diff)

comment:18 in reply to: ↑ 17 Changed 6 years ago by andrew.mathas

In response to Simon, the main bottleneck at the moment is the glacial pace of my reviewing. I will try get through this more quickly. In any case, I think that Travis and I will get the chance to sort this out face-to-face in ICERM in about two weeks so the patch should get a positive review by mid February at the latest.

Replying to tscrim:

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?

In spite of misgivings (maybe this is too strong!:) about the orders, I haven't yet found a way to do this that I am more comfortable with. Certainly one aspect that I don't like about the current implementation is that by having the option checking inside lt etc I am worried that this will have a significant cost when sorting a large number of partitions (I need to profile and check). If the orderings were made into a separate ticket this would definitely speed things up -- and I would volunteer to review the extra ticket.

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

No, nothing major. So far just a few missing bits of documentation and there's a few conventions that I thought I'd put to the vote on sage-combinat. Apart from this, I would prefer that there was a more generic way to take care of the class options but if this ever does come into existence then what you have done could easily be rebased on top of it.

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

Australia is still in holiday mode:) A.

comment:19 Changed 6 years ago by andrew.mathas

As I said above, I was concerned that patch might increase the time that it takes to compare partitions because the new order option manifests itself as a series of if-then-else statements inside each of the comparison functions lt, le etc. I just did some timings on 5.5 to see if there is a significant difference in sorting speeds.

The short answer is that sorting appears to be almost 3 times slower with the patch.

It could be that my test is not the best, so please feel free to suggest a better one.

With the patch applied:

sage: parts=list(Partitions(50));  
sage: %timeit parts.sort()
5 loops, best of 3: 627 ms per loop

Without the patch applied:

sage: parts=list(Partitions(50));   
sage: %timeit parts.sort()
5 loops, best of 3: 221 ms per loop

Rather than having the if-then-else structure inside the comparison functions there would be less overhead using somethng like the syntax used for _repr_:

def __lt__(self, other):
    return getattr(self, '__lt__'+partition_options['order'])(self, other)

Of course, this won't work at the moment as order is not an option...

comment:20 follow-up: Changed 6 years ago by andrew.mathas

Looking more at the orderings the following behaviour strikes me as being counter intuitive and confusing:

sage: mu=Partition([5,4])
sage: Partitions(order='dominance')(mu) in Partitions(9)
True
sage: Partitions(order='dominance')(mu) < Partitions(9)(mu)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/usr/local/src/sage/sage-5.5/devel/sage-combinat/sage/combinat/<ipython console> in <module>()

/usr/local/src/sage/sage-5.5/local/lib/python2.7/site-packages/sage/combinat/partition.pyc in __lt__(self, other)
    632             order = self.parent().order()
    633             if order != other.parent().order():
--> 634                 raise TypeError("orders must be the same")
    635             elif order == "lex":
    636                 return self._list.__lt__(other._list)

TypeError: orders must be the same

If the ordering really is "part" of the elements then, above, I think that we should have the following behaviour:

sage: Partitions(order='dominance')(mu) in Partitions(9)
False

Two other (minor) things that I don't like about the current way the orderings are done are:

  • the name "lex" and '"rev_lex" should really be "lexicographic" and "reverse lexicographic", but accept shorthands. Having order[:3] == 'lex' etc would solve this.
  • I don't really like have to use Partitions(order="...")  for some orderings and reverse(Partitions(order="...")) for others. I think that each of the ordering should allow a reverse modifier: so Partitions(order='dom') and Partitions(order='rev dom') should both be OK.

comment:21 in reply to: ↑ 20 Changed 6 years ago by tscrim

Hey Andrew,

Replying to andrew.mathas:

Looking more at the orderings the following behaviour strikes me as being counter intuitive and confusing:

sage: mu=Partition([5,4])
sage: Partitions(order='dominance')(mu) in Partitions(9)
True
sage: Partitions(order='dominance')(mu) < Partitions(9)(mu)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
TypeError: orders must be the same

If the ordering really is "part" of the elements then, above, I think that we should have the following behaviour:

sage: Partitions(order='dominance')(mu) in Partitions(9)
False

Good point. This should definitely be the correct behavior.

Two other (minor) things that I don't like about the current way the orderings are done are:

  • the name "lex" and '"rev_lex" should really be "lexicographic" and "reverse lexicographic", but accept shorthands. Having order[:3] == 'lex' etc would solve this.
  • I don't really like have to use Partitions(order="...")  for some orderings and reverse(Partitions(order="...")) for others. I think that each of the ordering should allow a reverse modifier: so Partitions(order='dom') and Partitions(order='rev dom') should both be OK.

As for the slowdown, I don't think it's not the if statements per-say, but all of the string comparisons done. However from a code maintenance standpoint, it might be better to do something like the following:

def __init__(self, ...):
    ...
    if order == 'lex':
        __gt__ = compare_lex
    elif order == 'dominance':
        __gt__ = dominated
    ...

def __lt__(self, other):
    return other.__lt__(self)

def __ge__(self, other):
    if other == self:
        return True
    return self.__lt__(other)

and so on.

I've created a new ticket for the options at #14013 and will upload the separated patches to the respective tickets along with the other requested changes within a few days. Also here's a link to Andrew's topic on sage-combinat-devel:

https://groups.google.com/forum/?fromgroups=#!topic/sage-combinat-devel/40YJR38-VU0

Thanks,
Travis

comment:22 Changed 6 years ago by andrew.mathas

Hi Travis,

One aspect of the options code that I don't like at the moment is that some of the options are only accessible if you change or set the corresponding global option. For example, there are five different options for TeX-ing partitions (and friends) but there is no easy way for an external class to access these individual options.

I can see three alternatives here:

  1. Don't worry about this and leave everything as it is.
  2. Have the option as a optionable argument to the method using something like:
    def _latex_(self, latex=None):
        if latex is None: latex=partition_options['latex']
        ...
    
    This has the advantage that it won't be necessary to have a plethora of minor variations for the different options of the method.
  3. Implement each option as a separate method as has been done for _repr_ and then define the optionable method using something like
    def _latex_(self):
        return getattr(self,'_latex_'+self.options['latex'])()
    
    This has the advantage that you could check generically to see whether an option was a valid option by checking hasattr(self,'_latex_'+self.optionslatex?) when the option is changed.

The reason that I care about this is that I have a class which wants to use particular TeX and display options for partitions -- namely, a class for displaying matrices which which have rows and columns indexed by particular partitions. As it is currently written, the only way that my class will able to access the latex methods it wants is by playing silly games with partition_options. As partitions and tableaux are widely used as indices I would think that there will be other examples eventually.

A second point, as above, I think that none of the "option clients" should ever access partition_options and tableau_options directly. Rather, they should call self.options() or self.parent().options() to do this.

Let me know what you think about these. I can fold your answer into my review patch.

Andrew

Last edited 6 years ago by andrew.mathas (previous) (diff)

comment:23 follow-up: Changed 6 years ago by andrew.mathas

Another two questions:

  1. In sage.combinat.tableau there is an optionable argument (currently *order* but I will deprecate this to) *convention* which defaults to "French". Now that there is a global option for choosing the *convention* I think that the default *convention* here should be tableau_optionsconvention?.

Although I think that this sounds sensible one consequence of doing this is that the default option will change from "French" to "English".

What do you think?

  1. Secondly, should skew_tableau and ribbon_tableau care about tableau_options? This could just be added as a TODO:

Andrew

Last edited 6 years ago by andrew.mathas (previous) (diff)

comment:24 in reply to: ↑ 23 ; follow-up: Changed 6 years ago by tscrim

Hey Andrew,

Replying to andrew.mathas:

One aspect of the options code that I don't like at the moment is that some of the options are only accessible if you change or set the corresponding global option. For example, there are five different options for TeX-ing partitions (and friends) but there is no easy way for an external class to access these individual options.

I can see three alternatives here:

  1. Don't worry about this and leave everything as it is.
  2. Have the option as a optionable argument to the method using something like:
    def _latex_(self, latex=None):
        if latex is None: latex=partition_options['latex']
        ...
    
    This has the advantage that it won't be necessary to have a plethora of minor variations for the different options of the method.
  3. Implement each option as a separate method as has been done for _repr_ and then define the optionable method using something like
    def _latex_(self):
        return getattr(self,'_latex_'+self.options['latex'])()
    
    This has the advantage that you could check generically to see whether an option was a valid option by checking hasattr(self,'_latex_'+self.optionslatex?) when the option is changed.

Since we are advertising (for lack of a better word) #3 as a general design pattern, I'm going with that. Plus it makes easy to access a particular latex output you want and is very extendable. I've done this for Partition currently.

The reason that I care about this is that I have a class which wants to use particular TeX and display options for partitions -- namely, a class for displaying matrices which which have rows and columns indexed by particular partitions. As it is currently written, the only way that my class will able to access the latex methods it wants is by playing silly games with partition_options. As partitions and tableaux are widely used as indices I would think that there will be other examples eventually.

However the major point of the options is so you can customize the output to what you want. Since partitions would be the indices for your matrix, I would want the matrix's indices output to depend on what I set in the partition options. A place where you might want to call a specific latex output would be something like a StrictlyDecreasingIntegers (I'm sorry it's somewhat of a contrived example) class which would inherit from Partition but only has meaning as a list.

A second point, as above, I think that none of the "option clients" should ever access partition_options and tableau_options directly. Rather, they should call self.options() or self.parent().options() to do this.

Then how would you allow global access? I don't think these dictionaries should be private (and/or name-mangled) to Partitions (and Tableaux) because it indicates (to me) the options are only bound to Partitions, and that they don't have a global impact (such as to PartitionTuple). I think we should have the option() method to PartitionTuples and any other class that wants access to options.

Actually, I just had a thought. I think we need an abstract class PartitionOptions which holds the name-mangled dictionary and only accessible through a method options(). Thus any class which wants to use the partition options must also inherit from PartitionOptions. (Similarly for TableauxOptions of course.) Is this what you were thinking of?

Replying to andrew.mathas:

Another two questions:

  1. In sage.combinat.tableau there is an optionable argument (currently *order* but I will deprecate this to) *convention* which defaults to "French". Now that there is a global option for choosing the *convention* I think that the default *convention* here should be tableau_options['convention'].

Although I think that this sounds sensible one consequence of doing this is that the default option will change from "French" to "English".

What do you think?

I'm guessing you're referring to from_shape_and_word(). I thought about this, and in an ideal world, the default argument would be None which just pulls from the partition options. However, I'm thinking methods such as to_word() should also do the same first. Also somewhere in promotion in the crystals code uses this, and I think (it was awhile ago) I tried overriding this back to French but it still was broken. So I just left this alone.

  1. Secondly, should skew_tableau and ribbon_tableau care about tableau_options? This could just be added as a TODO:

Yes, and same for skew_partition (which doesn't have a proper latex method yet...I probably should write this...) and ribbon.

Thanks,
Travis

comment:25 follow-up: Changed 6 years ago by tscrim

  • Description modified (diff)

Also in case you (or anyone else) is wondering, the tex_from_array() method handles the convention option.

comment:26 in reply to: ↑ 25 Changed 6 years ago by andrew.mathas

Replying to tscrim:

Also in case you (or anyone else) is wondering, the tex_from_array() method handles the convention option.

Yes, I noticed this but I wasn't completely convinced this was a good idea because tex_from_array is generic and it can be called by anything. If there were uses which had nothing to do with partitions or tableaux this would be a little strange. I think it's is OK as it is currently used only by these two classes, however, I'll add a warning about this to the documentation.

Last edited 6 years ago by andrew.mathas (previous) (diff)

comment:27 in reply to: ↑ 24 ; follow-up: Changed 6 years ago by andrew.mathas

Hi Travis,

Replying to tscrim:

However the major point of the options is so you can customize the output to what you want. Since partitions would be the indices for your matrix, I would want the matrix's indices output to depend on what I set in the partition options. A place where you might want to call a specific latex output would be something like a StrictlyDecreasingIntegers (I'm sorry it's somewhat of a contrived example) class which would inherit from Partition but only has meaning as a list.

I don't fully agree because I think that when one object is used by another object then it takes on different characteristics so that the global defaults may not necessarily make sense or may be overridden by other constraints. For example, the labels for my matrices need to print on one line so using the diagram _repr_'s would break the table _repr_.

With methods like _latex_ my table does use the global default BUT the idea is that it will be possible to further override these as options to the table.

A second point, as above, I think that none of the "option clients" should ever access partition_options and tableau_options directly. Rather, they should call self.options() or self.parent().options() to do this.

Then how would you allow global access? I don't think these dictionaries should be private (and/or name-mangled) to Partitions (and Tableaux) because it indicates (to me) the options are only bound to Partitions, and that they don't have a global impact (such as to PartitionTuple). I think we should have the option() method to PartitionTuples and any other class that wants access to options.

Sorry, my bad, I played around a little with a generic options class which let you do things like this. It was derived from UniqueRepresentation? which allowed it to be used by multiple classes, but I decided that this wasn't really workable as to get all of the features I wanted in a generic options class the syntax became too contrived. I like your idea of a PartitionsOptions? class.

Andrew

Last edited 6 years ago by andrew.mathas (previous) (diff)

comment:28 in reply to: ↑ 27 Changed 6 years ago by tscrim

Hey Andrew,

Replying to andrew.mathas:

Replying to tscrim:

However the major point of the options is so you can customize the output to what you want. Since partitions would be the indices for your matrix, I would want the matrix's indices output to depend on what I set in the partition options. A place where you might want to call a specific latex output would be something like a StrictlyDecreasingIntegers (I'm sorry it's somewhat of a contrived example) class which would inherit from Partition but only has meaning as a list.

I don't fully agree because I think that when one object is used by another object then it takes on different characteristics so that the global defaults may not necessarily make sense or may be overridden by other constraints. For example, the labels for my matrices need to print on one line so using the diagram _repr_'s would break the table _repr_.

That's a good point about _repr_(). However what might happen with #14040 might change things... (but it's moot anyways because we have the _repr_*() as easy access for the user's specific choice.)

With methods like _latex_ my table does use the global default BUT the idea is that it will be possible to further override these as options to the table.

When necessary, I agree with you (hence the change to _latex_*() similar to _repr_*()).

Then how would you allow global access? I don't think these dictionaries should be private (and/or name-mangled) to Partitions (and Tableaux) because it indicates (to me) the options are only bound to Partitions, and that they don't have a global impact (such as to PartitionTuple). I think we should have the option() method to PartitionTuples and any other class that wants access to options.

Sorry, my bad, I played around a little with a generic options class which let you do things like this. It was derived from UniqueRepresentation? which allowed it to be used by multiple classes, but I decided that this wasn't really workable as to get all of the features I wanted in a generic options class the syntax became too contrived. I like your idea of a PartitionsOptions? class.

I will talk with Nicolas about this tomorrow. Nonetheless, I won't touch the partition options patch in the combinat queue again (sorry, I hope I didn't cause you to have a huge rebase for the review patch) until you are done with your review patch.

Thanks,
Travis

comment:29 follow-up: Changed 6 years ago by tscrim

Hey Andrew,

I talk with Nicolas about the options, and the short version is that we should not create a new superclass for the options since it would only add 1 or 2 methods. As for the actual implementation of the options, that we should pick a convention and stick to that. So, should we just keep the way things are now?

Thanks,
Travis

comment:30 Changed 6 years ago by tscrim

Also, I'm going to make this a dependency of #10193 (the combinat queue will have this change once your review patch is up).

comment:31 Changed 6 years ago by tscrim

  • Dependencies changed from #13074 #13762 #13840 #10193 to #13074 #13762 #13840

comment:32 in reply to: ↑ 29 Changed 6 years ago by andrew.mathas

Replying to tscrim:

I talk with Nicolas about the options, and the short version is that we should not create a new superclass for the options since it would only add 1 or 2 methods. As for the actual implementation of the options, that we should pick a convention and stick to that. So, should we just keep the way things are now?

OK, I'm happy with this. A.

comment:33 Changed 6 years ago by tscrim

  • Dependencies changed from #13074 #13762 #13840 to #13074 #13762 #13840 #14065

#14065 should fix the sorting.

Edit - Wrong ticket

Last edited 6 years ago by tscrim (previous) (diff)

comment:34 Changed 6 years ago by nbruin

Since the scope of what this ticket is supposed to accomplish seems to still be in flux, can you rebase it on top of #13991, which implements one small, well-defined bit of what is being done here? It's required to resolve a rather bad speed regression that otherwise happens with #12313, which is starting to become a dependency for a lot of essential infrastructure tickets.

comment:35 Changed 6 years ago by andrew.mathas

Hi Travis,

Not sure that I will be able to upload to the queue from the airport, but I've found two problems that I can't see an easy fix for. Quite possibly you have already fixed them, but please try:

TestSuite( OrderedPartitions(5,3) ).run(
TestSuite( Partitions(5, min_part=2) ).run()

Both of them give errors for me.

Apart form this I have finished my review. I'll have to have a look over the changes that you have made and someone will have to review my review as it has gotten quite large -- as I discussed with you and Nicolas, I have replaced your partition and tableau options with a general global_options class and I also fixed up tex_from_array so that it now copes with arbitrary skew composition tuples.

Will upload to trac and the queue as soon as I am able, but this probably won't be until Monday Sydney time due to the connection here -- and I first need to rebase over your changes.

Cheers., Andrew

Last edited 6 years ago by andrew.mathas (previous) (diff)

Changed 6 years ago by andrew.mathas

Review patch which primarily imporves option handling and fixes tex_from_array

comment:36 Changed 6 years ago by andrew.mathas

  • Keywords days45 added

The patch is good except for two TestSuite? failures above which come down to the following:

sage: [5]  in Partitions(5, min_part=2)       
True
sage: Partition([5])  in Partitions(5, min_part=2)
False
sage: [3,1,1] in OrderedPartitions(5,3)
True
sage: Partition([3,1,1]) in OrderedPartitions(5,3)
False

They look like they are both the same issue with IntegerListsLex?, but I couldn't see how to fix this. Once these problems are fixed -- and once some one reviews my review patch -- I am happy to give this a positive review.

Last edited 6 years ago by andrew.mathas (previous) (diff)

comment:37 Changed 6 years ago by andrew.mathas

Given my review patch is so long I thought that I ought to document what it does:

  • defines a generic GlobalOptions? class in sage.structure.global_options which replaces the previous dictionaries partition_options and tableau_options and provides more features for them.
  • adds the missing option variations for PartitionTuple? and TableauTuple? together with doc-tests for them
  • rewrites tex_from_array in sage.combinat.output so that it now returns valid latex for drawing the diagrams of arbitrary "skew composition" shape. The code is much cleaner, and the latex produced is shorter, with the consequence that many doc-tests across many files had to be updated.
  • small reorganisation of the partition like objects in the reference manual as discussed on sage-combinat
  • adds TestSuite? calls to the new parent/element classes
  • minor tweaks and fixes
Last edited 6 years ago by andrew.mathas (previous) (diff)

comment:38 Changed 6 years ago by tscrim

  • Dependencies changed from #13074 #13762 #13840 #14065 to #14065 #13688
  • Description modified (diff)

I've folded the review patch and should have fixed up everything. Nicolas is willing do the final look-over of the patch. After that, this should be done. Thank you both for your work on getting this reviewed.

The dependency on #13688 is for cardinality tests in partitions.

For patchbot:

Apply: trac_13605-partition_options-ts.patch

comment:39 Changed 6 years ago by tscrim

  • Dependencies changed from #14065 #13688 to #14065 #14063 #13688

comment:40 Changed 6 years ago by tscrim

  • Dependencies changed from #14065 #14063 #13688 to #14065 #6495 #14063 #13688

comment:41 Changed 6 years ago by andrew.mathas

  • Description modified (diff)

comment:42 Changed 6 years ago by tscrim

I added the dependency on #6495 and updated the patch accordingly.

For patchbot:

Apply: trac_13605-partition_options-ts.patch

comment:43 follow-up: Changed 6 years ago by nthiery

Hi!

I went through roughly the first half of the patch. Altogether it's good!

I just posted a reviewer's patch on the patch server, mostly to follow the guidelines of the developpers manual. Please have a look at my changes; similar ones probably need to be done in the rest of the patch. Note that I also did a couple changes directly in Travis's version of the patch on the queue.

One thing that would need a small clarification: there is some duplication between the documentation of the "global_options" module and the "GlobalOptions?" class. That's not necessarily bad since they can serve different roles (tutorial/reference). But this should be stated explicitly with appropriate cross references.

Thanks!

Nicolas

comment:44 in reply to: ↑ 43 ; follow-up: Changed 6 years ago by andrew.mathas

Hi Nicolas,

Replying to nthiery:

I just posted a reviewer's patch on the patch server, mostly to follow the guidelines of the developpers manual. Please have a look at my changes; similar ones probably need to be done in the rest of the patch. Note that I also did a couple changes directly in Travis's version of the patch on the queue.

Mostly this seems to be adding missing input statements to the code that I wrote for global options. As Travis wrote the rest of patch, probably everything else is OK:)

One thing that would need a small clarification: there is some duplication between the documentation of the "global_options" module and the "GlobalOptions?" class. That's not necessarily bad since they can serve different roles (tutorial/reference). But this should be stated explicitly with appropriate cross references.

I have been through and added some links in GlobalOptions?. Part of the duplication is between the module documentation and the documentation for the methods. However, as almost all of the methods have names beginning with an underscore they won't appear in the reference manual. This means that, as far as the reference manual is concerned, there is very little overlap.

I have just pushed the a modification of Nicolas' review patch to the queue.

Andrew

comment:45 Changed 6 years ago by andrew.mathas

I noticed that the indentation in documentation generated by a GlobablOptions? class was incorrect. The problem is that because the initial and final parts of the documentation are passed to GlobalOptions? as strings the documentation gets confused if strings have uneven white space at the start of different lines.

I have just pushed a second version of Nicolas' review patch to the combinat queue which addresses this.

Secondly, I noticed that the documentation for sage.structure.global_options contains the links

    :meth:`~sage.combinat.partition.Partitions.global_options` and
    :meth:`~sage.combinat.tableau.Tableaux.global_options`.

Unfortunately, these do not display as links in the manual. Similarly, the auto generated doc-strings for a GlobalOption? end with

See :class:`~sage.structure.global_options.GlobalOptions` for more features of these options.

and this prints as GlobalOptions? in the manual and, again, there is no link to the relevant section of the manual. See Partitions.global_options.

I thought in all of these cases a link should appear, but none of variations of this that i have tried make the link appear.

Hopefully this is caused by my local configuration...if not, then this is a minor bug...

Last edited 6 years ago by andrew.mathas (previous) (diff)

comment:46 Changed 6 years ago by tscrim

  • Reviewers changed from Andew Mathas to Andew Mathas, Nicolas Thiery
  • Status changed from needs_review to positive_review

I've been back over it and I think it's now good to go so I'm setting this to positive review. Thank you both for your work on this.

Travis

For patchbot:

Apply: trac_13605-partition_options-ts.patch

comment:47 in reply to: ↑ 44 Changed 6 years ago by nthiery

Replying to andrew.mathas:

Mostly this seems to be adding missing input statements to the code that I wrote for global options.

Yup, and a bunch of other minor things like starting the doc string with a one-line title, starting with "Return" (no s) and ending with a ".". And not adding spaces at the end of lines. Etc.

Cheers,

Nicolas

comment:48 Changed 6 years ago by tscrim

  • Dependencies changed from #14065 #6495 #14063 #13688 to #14065 #6495 #14063 #13688 #14138

Rebased over #14138 and removed deprecation issued in that patch since this inadvertently fixed the problem.

Changed 6 years ago by tscrim

Minor rebase to 5.8.beta1

comment:49 Changed 6 years ago by tscrim

Minor rebase to 5.8.beta1.

For patchbot:

Apply only: trac_13605-partition_options-ts.patch

Last edited 6 years ago by tscrim (previous) (diff)

comment:50 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:51 Changed 6 years ago by andrew.mathas

  • Reviewers changed from Andew Mathas, Nicolas Thiery to Andrew Mathas, Nicolas Thiery

comment:52 Changed 6 years ago by nthiery

  • Reviewers changed from Andrew Mathas, Nicolas Thiery to Andrew Mathas, Nicolas M. Thiéry

comment:53 Changed 6 years ago by leif

Minor remark:

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

  • sage/combinat/sf/k_dual.py

    diff --git a/sage/combinat/sf/k_dual.py b/sage/combinat/sf/k_dual.py
    a b from sage.misc.cachefunc import cached_m 
    3939from sage.categories.magmas import Magmas
    4040from sage.misc.constant_function import ConstantFunction
    4141from sage.categories.graded_hopf_algebras_with_basis import GradedHopfAlgebrasWithBasis
    42 from sage.combinat.partition import Partition, Partitions, Partition_class
     42from sage.combinat.partition import Partition, Partitions, Partition
    4343from sage.rings.all import Integer
    4444from sage.combinat.combinat import InfiniteAbstractCombinatorialClass
    4545import sage.combinat.sf.sfa as sfa

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

comment:54 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.8.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:55 follow-up: Changed 5 years ago by novoselt

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"?

comment:56 Changed 5 years ago by tscrim

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.

comment:57 in reply to: ↑ 55 Changed 5 years ago by andrew.mathas

Replying to novoselt:

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

This is addressed in Travis' patch #14248.

Note: See TracTickets for help on using tickets.