#13605: Partition options and cleanup partitions documentation
-----------------------------------------------+----------------------------
Reporter: tscrim | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.6
Component: combinatorics | Resolution:
Keywords: partition, options, output | Work issues:
Report Upstream: N/A | Reviewers: Andew Mathas
Authors: Travis Scrimshaw | Merged in:
Dependencies: #13074 #13762 #13840 #10193 | Stopgaps:
-----------------------------------------------+----------------------------
Comment (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 [comment:12 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 [comment:13 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,[[BR]]
Travis
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13605#comment:15>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
