Opened 23 months ago

Closed 18 months ago

Last modified 18 months ago

#13072 closed enhancement (fixed)

Implementation of PartitionTuple + some minor fixes to partition.py

Reported by: andrew.mathas Owned by: Andrew Mathas
Priority: major Milestone: sage-5.5
Component: combinatorics Keywords: tuples of partitions
Cc: sage-combinat Merged in: sage-5.5.beta1
Authors: Andrew Mathas Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #9265, #11446 Stopgaps:

Description (last modified by jdemeyer)

This patch implements the following classes:

  • PartitionTuple - returns a tuple of partitions
  • PartitionTuples - factory class for all tuples of partitions
  • !PartitionTuples_level - class of all tuples of partition of a fixed level
  • !PartitionTuples_size - class of all tuples of partition of a fixed size
  • !PartitionTuples_level_size - class of all tuples of partition of a fixed level and size. The first three of these are infinite enumerated classes whereas the last is finite. They all have iterators.

The idea is to implement a fully function class for PartitionTuples as I currently need this together with a class for tuples of (standard) tableaux (coming soon).

PartitionTuples of level 1 are in natural bijection with Partitions so when given a 1-tuple of partitions, or a partition, PartitionTuples() returns the corresponding Partition. This works almost seamlessly, making it possible to almost ignore the distinction between Partitions() and PartitionTuples(). One exception is that the expected behaviour of

     for component in mu: 
          do X

is different for partitions and partition tuples (in the first case, you expect to loop over the parts of the partition and in the second over the components of the tuple). To get around this both classes now have a components() method so that you can uniformly write

for nu in mu.components():
      do X

Improvements welcome!

In terms of implementation, for my use of these objects the level is more intrinsic than the size so I have set the syntax for the PartitionTuples? classes as

PartitionTuples(level=l, n=n)

where level and n are both optional named arguments BUT level is specified first. Previously, n was given first and level second. I think that it makes much more sense this way around, but if people feel really strongly about this I will change it back. Previously, level was just called k, which is a fairly random variable whereas level makes sense in terms of categorification and higher level Fock spaces. (Replacing n with size would also be sensible but I didn't go there.)

Deprecations of old functions: Finally, in addition to these new classes I have removed a bunch functions which were depreciated years ago and depreciated some more functions, as discussed on sage-combinat. I also reinstated the beta_numbers() methods which were removed in the last patch to partition.py (this patch said that beta_numbers and frobenius_coordinates are identical objects, but they are actually different).

For discussion about the functions being deprecated please see the following two discussions on sage-combinat:

Below is a summary of the above listed in order of what I think is decreasing controversy.

  1. A=sage.combinat.partition.number_of_partitions() is marked for deprecation in favour of B=sage.combinat.partitions.number_of_partitions(), which is what function A() calls most of the time. As agreed above, number_of_partitions() will stay in the global name space, but this made the deprecation somewhat fiddly as I did not want to deprecate number_of_partitions() for "normal use" because from the user perspective this function will not change. Instead, I have deprecated the individual options of number_of_partitions() so deprecation warnings are only generated when A() does NOT call B(). In the global namespace, number_of_partitions still points to A(). When the functions which are marked for deprecation below are removed, number_of_partitions() should be changed to point to B() and A() should be changed into a deprecated_function_alias to B(). See the patch for more details.
  1. For use in Partitions().random_element() the function number_of_partitions() was cached. This cached function was almost never used so, assuming that caching this function is a good idea, I decided to use a cached version of number_of_partitions() inside partition.py always. As shown in the comments below, this leads to a dramatic speed-up.

This probably should be revisited when Fredrik Johansson's patch #13199, which uses FLINT to implement a faster version of number_of_partitions, is merged into sage.

  1. The two functions
    • cyclic_permutations_of_partition
    • cyclic_permutations_of_partition_iterator

are deprecated in sage.combinat.partition and they have been moved to sage.combinat.set_partition and renamed ...._of_set_partition... As far as I can tell these functions are never used but, in any case, they are methods on set partitions rather than partitions. Nonetheless, they need to be deprecated from the global name space.

  1. The following functions were marked for deprecation several years ago so they have been removed from sage.combinat.partition.py:
    • partitions_list
    • number_of_partitions_list
    • partitions_restricted
    • number_of_partitions_restricted
  1. For the reasons given in #5478, RestrictedPartitions? was also slated for removal but it was decided not to deprecate this class until Partitions() is able to process the appropriate combinations of keyword arguments. See #12278 and the comment by John Palmieri below for more details. Nicolas has suggested that one way of addressing this may be to refactor the partitions code so that it uses Florent's enumerated sets factories #10194.
  1. The following functions now give deprecation warnings and they are marked for removal from the global name space:
    • partitions_set
    • number_of_partitions_set
    • ordered_partitions
    • number_of_ordered_partitions
    • partitions,
    • ferrers_diagram
    • partitions_greatest
    • partitions_greatest_eq
    • partitions_tuples
    • number_of_partitions_tuples
    • partition_power

In all cases, these function are deprecated in favour of (methods in) parent classes.

Apply: trac_13072-tuples-of-partitions_am.patch

Attachments (1)

trac_13072-tuples-of-partitions_am.patch (241.9 KB) - added by andrew.mathas 18 months ago.
Adding proper commit message

Download all attachments as: .zip

Change History (56)

comment:1 Changed 22 months ago by andrew.mathas

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 22 months ago by andrew.mathas

  • Work issues Some category tests currently fails. deleted

comment:3 Changed 21 months ago by andrew.mathas

  • Dependencies changed from NA to #9265
  • Description modified (diff)
  • Priority changed from minor to major

Should now apply cleanly to sage 5.2

comment:4 Changed 21 months ago by andrew.mathas

  • Description modified (diff)

comment:5 Changed 21 months ago by andrew.mathas

Apply trac_13072-tuples-of-partitions_am.patch

Last edited 21 months ago by andrew.mathas (previous) (diff)

comment:6 Changed 21 months ago by andrew.mathas

  • Description modified (diff)

comment:7 Changed 21 months ago by andrew.mathas

New version of patch which creates a new file partition_tuple.py which contains all of the partition_tuple code.

comment:8 Changed 21 months ago by andrew.mathas

For the patchbot:

Apply trac_13072-tuples-of-partitions_am.patch

comment:9 Changed 20 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

comment:10 Changed 20 months ago by andrew.mathas

  • Description modified (diff)

comment:11 Changed 20 months ago by andrew.mathas

For the patchbot:

Apply trac_13072-tuples-of-partitions_am.patch

comment:12 Changed 20 months ago by andrew.mathas

  • Description modified (diff)

comment:13 Changed 20 months ago by andrew.mathas

  • Description modified (diff)

comment:14 Changed 20 months ago by andrew.mathas

  • Description modified (diff)

The following timings show that there is a dramatic speed-up when number_of_partitions is cached:

With caching:

sage: %timeit [Partitions(n).random_element() for n in range(100)]
25 loops, best of 3: 25 ms per loop
sage: %timeit [Partitions(n).random_element() for n in range(100)]
25 loops, best of 3: 24.6 ms per loop
sage: %timeit [Partitions(n).random_element() for n in range(100)]
25 loops, best of 3: 25.4 ms per loop

Without caching:

sage: %timeit [Partitions(n).random_element() for n in range(100)]
5 loops, best of 3: 1.23 s per loop
sage: %timeit [Partitions(n).random_element() for n in range(100)]
5 loops, best of 3: 1.23 s per loop
sage: %timeit [Partitions(n).random_element() for n in range(100)]
5 loops, best of 3: 1.26 s per loop

comment:15 Changed 20 months ago by andrew.mathas

  • Description modified (diff)

comment:16 follow-up: Changed 20 months ago by jhpalmieri

Regarding RestrictedPartitions: see #12278. Should it be deprecated at all? In particular, what's the replacement for something like RestrictedPartitions(5,[3,2,1], 3)? The best I can come up with is

[p for p in Partitions(5, parts_in=[3,2,1]) if len(p) == 3]

but surely this isn't ideal.

Last edited 20 months ago by jhpalmieri (previous) (diff)

comment:17 Changed 20 months ago by andrew.mathas

  • Description modified (diff)

comment:18 Changed 20 months ago by andrew.mathas

  • Description modified (diff)

comment:19 Changed 20 months ago by andrew.mathas

For the patchbot:

Apply trac_13072-tuples-of-partitions_am.patch

comment:20 Changed 20 months ago by andrew.mathas

  • Description modified (diff)

comment:21 Changed 20 months ago by andrew.mathas

  • Description modified (diff)

comment:22 Changed 19 months ago by andrew.mathas

  • Description modified (diff)

comment:23 Changed 19 months ago by andrew.mathas

For the patchbot:

Apply trac_13072-tuples-of-partitions_am.patch

comment:24 in reply to: ↑ 16 Changed 19 months ago by andrew.mathas

Replying to jhpalmieri:

Regarding RestrictedPartitions: see #12278. Should it be deprecated at all? In particular, what's the replacement for something like RestrictedPartitions(5,[3,2,1], 3)? The best I can come up with is

[p for p in Partitions(5, parts_in=[3,2,1]) if len(p) == 3]

but surely this isn't ideal.

This was discussed in detail on sage-combinat, eventually leading to point #5 in the blurb for this ticket.

comment:25 Changed 19 months ago by tscrim

  • Dependencies changed from #9265 to #9265, #11446
  • Status changed from needs_review to positive_review

Looks good. I've added #11446 as a dependency since this is based respect to #11446 and it's dependency #11442 (both slightly modify partition.py as well).

Last edited 19 months ago by tscrim (previous) (diff)

comment:26 follow-up: Changed 19 months ago by hivert

  • Status changed from positive_review to needs_work

Hi Andrew and Travis,

Thanks both for your work. I'm hate to switch back to needs works but looking at the compiled doc, I see various small problems which should be fixed. Here are some of them:

  • Don't indent bulleted list. It adds an extra uneeded indentation (see e.g. REFERENCE vs AUTHORS in the module class;
  • There is a proper markup for references (see developper guide);
  • In the doc of the class PartitionTuple, there is a miss indentation between INPUT and EXAMPLES:
  • in the doc of Garnir_tableau please write ``self`` ``cell``, ``FALSE`` ... (verbatim set-up) but don't forget single back-quote for `(k,a+1,c)` (latex set-up) and similar. The hyperlink in SEE ALSO are missing
  • There is a proper markup for linking to trac ticket eg: :trac:`13123`
  • There is a typo in "The Garnir tableau are the “first” non-standard tableaux which arise when you at by simple transpositions."

Sorry for being picky for the doc. If it wasn't so late et France, I would have written a review patch.

For Travis: please check the compiled doc when your are reviewing a patch. You can refer to http://wiki.sagemath.org/ReviewChecklist.

Cheers,

Florent

comment:27 in reply to: ↑ 26 ; follow-up: Changed 19 months ago by andrew.mathas

Hi Florent,

Thanks for the specific comments about what needs to be fixed. I'll go through and fix these.

For Travis: please check the compiled doc when your are reviewing a patch. You can refer to http://wiki.sagemath.org/ReviewChecklist.

Actually, Travis has already spent a large amount of time fixing my doc strings, so there would be many more problems without the large amount of time that he has already spent on this.

Andrew

comment:28 Changed 19 months ago by andrew.mathas

Hi Florent,

I think that the revised patch fixes all of the problems that you highlighted -- well, except for the Garnir tableaux issues which are in #13074.

Cheers, Andrew

comment:29 in reply to: ↑ 27 ; follow-up: Changed 19 months ago by hivert

Hi Andrew,

Replying to andrew.mathas:

Actually, Travis has already spent a large amount of time fixing my doc strings, so there would be many more problems without the large amount of time that he has already spent on this.

Sorry, I you feel I'm being rude. It wasn't my intend. However, I've no chance to know that since there is no record of his work on this ticket. Even when the review is done offline, it is good to keep a (not necessarily detailed) trace of what has been done on the ticket, if only to give proper credit.

Cheers,

Florent

PS: Unfortunately, I've no time to answer your comment on #13074, right now (run to catch a train + teaching).

comment:30 in reply to: ↑ 29 Changed 19 months ago by andrew.mathas

Hi Florent,

No, no, that's OK. I just wanted to acknowledge that Travis has done a lot of work on the documentation and that any errors that remained were mine and mine alone. I appreciate your looking at the patch and trying to improve it.

I have mostly sorted out the doc string problems in these two patches but there are till one or two that remain. If there is any trick to working out where the errors appear in the code from the rest errors messages please let me know when you have the time as currently I am doing pseudo random searches.

Thanks again, Andrew

comment:31 Changed 19 months ago by andrew.mathas

I think that all of the doc string issues really are fixed now.

comment:32 Changed 19 months ago by tscrim

Florent,

Thank you for catching these docstring problems. I appreciate you begin picky about the docs. I didn't know about the indentation of the bullet lists, and I did miss that indentation of EXAMPLES:: block in the compiled doc.

Andrew,

A few more minor issues.

  • I believe this line (line 263 in partition_tuple.py) has a comma misplaced:
    When these algebras are not semisimple partition, tuples index...
    
  • In partition_tuple.hook_length() it should be coordinates of the form `(k,r,c)`
  • In partition.random_element(), the inputs uniform and Plancherel should be indented one more since they are the types of inputs for measure.

comment:33 Changed 19 months ago by andrew.mathas

Hi Travis,

I have uploaded a new version of the patch which fixes the errant comma and the indentation in random_element but I think that the ``(k,r,c)`` in the hook_length function is correct because k,r and c are arguments to this function. Of course, it would be more correct to write (``k``,``r``,``c``) but ReST complains about this. I guess that (``k``, ``r``, ``c``) might be OK, although I suspect that it will want a few more spaces like ( ``k`` , ``r`` , ``c`` ) to be legal syntax. I prefer using ``(k,r,c)`` as these three integers together comprise a cell which is really a "single" variable... Let me know if you disagree.

Cheers, Andrew

comment:34 Changed 19 months ago by tscrim

Hey Andrew,

Yes, it should be ``(k,r,c)`` but right now it is ``(r,c)``. Although on further thought, it might be better to move the note about 0-based (and adding ``k``) and the python *-operator to the header. That way it covers all of the similar functions.

Thanks, Travis

comment:35 Changed 19 months ago by andrew.mathas

Thanks Travis, you are right of course. I've updated the patch.

Andrew

--

For the patchbot:

Apply trac_13072-tuples-of-partitions_am.patch

Last edited 19 months ago by andrew.mathas (previous) (diff)

comment:36 Changed 19 months ago by tscrim

  • Status changed from needs_work to positive_review

Thanks Andrew! Looks good. I like the notes.

comment:37 Changed 19 months ago by jdemeyer

  • Milestone changed from sage-5.4 to sage-5.5

comment:38 Changed 19 months ago by jdemeyer

  • Description modified (diff)

comment:39 follow-up: Changed 19 months ago by jdemeyer

  • Status changed from positive_review to needs_work
sage -t  -force_lib devel/sage/sage/structure/sage_object.pyx
**********************************************************************
File "/release/merger/sage-5.5.beta0/devel/sage-main/sage/structure/sage_object.pyx", line 1114:
    sage: sage.structure.sage_object.unpickle_all()  # (4s on sage.math, 2011)
Expected:
    doctest:... DeprecationWarning: This class is replaced by Matrix_modn_dense_float/Matrix_modn_dense_double.
    See http://trac.sagemath.org/4260 for details.
    Successfully unpickled ... objects.
    Failed to unpickle 0 objects.
Got:
     * unpickle failure: load('/release/merger/sage-5.5.beta0/home/.sage/tmp/sage.math.washington.edu/5737/dir_i3wI40//pickle_jar/_class__sage_combinat_partition_PartitionTuples_nk__.sobj')
    doctest:1172: DeprecationWarning: This class is replaced by Matrix_modn_dense_float/Matrix_modn_dense_double.
    See http://trac.sagemath.org/4260 for details.
    Failed:
    _class__sage_combinat_partition_PartitionTuples_nk__.sobj
    Successfully unpickled 593 objects.
    Failed to unpickle 1 objects.
**********************************************************************

comment:40 Changed 19 months ago by jdemeyer

sage -t  --long -force_lib devel/sage/sage/combinat/partition.py
**********************************************************************
File "/release/merger/sage-5.5.beta0/devel/sage-main/sage/combinat/partition.py", line 434:
    sage: all(test2(core,tuple(mus))  # long time (5s on sage.math, 2011)
          for k in range(Integer(1),Integer(10))
          for n_core in range(Integer(10)-k)
          for core in Partitions(n_core)
          if core.core(k) == core
          for n_mus in range(Integer(10)-k)
          for mus in PartitionTuples(n_mus,k))
Exception raised:
    Traceback (most recent call last):
      File "/release/merger/sage-5.5.beta0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/release/merger/sage-5.5.beta0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/release/merger/sage-5.5.beta0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_5[6]>", line 2, in <module>
        for k in range(Integer(1),Integer(10))
      File "<doctest __main__.example_5[6]>", line 7, in <genexpr>
        for mus in PartitionTuples(n_mus,k))
      File "classcall_metaclass.pyx", line 279, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (sage/misc/classcall_metaclas
s.c:946)
      File "/release/merger/sage-5.5.beta0/local/lib/python/site-packages/sage/combinat/partition_tuple.py", line 1059, in __classcall_pri
vate__
        raise ValueError, 'the level must be a positive integer'
    ValueError: the level must be a positive integer
**********************************************************************

comment:41 in reply to: ↑ 39 ; follow-up: Changed 19 months ago by andrew.mathas

Hi Jeroen,

Perhaps I am confused, but most of these pickles shouldn't exist any more as they should have been removed by the new pickle jar attached to #9265. Specifically, the pickles

_class__ sage_combinat_skew_tableau_SemistandardSkewTableaux_n__ .sobj')
_class__ sage_combinat_skew_tableau_SemistandardSkewTableaux_nmu__ .sobj')
_class__ sage_combinat_skew_tableau_SemistandardSkewTableaux_p__ .sobj')
_class__ sage_combinat_skew_tableau_SemistandardSkewTableaux_pmu__ .sobj')
_class__ sage_combinat_skew_tableau_StandardSkewTableaux_n__ .sobj')
_class__ sage_combinat_tableau_SemistandardTableaux_n__ .sobj')
_class__ sage_combinat_tableau_SemistandardTableaux_nmu__ .sobj')
_class__ sage_combinat_tableau_SemistandardTableaux_p__ .sobj')
_class__ sage_combinat_tableau_SemistandardTableaux_pmu__ .sobj')
_class__ sage_combinat_tableau_StandardTableaux_n__ .sobj')
_class__ sage_combinat_tableau_StandardTableaux_partition__ .sobj')
_class__ sage_combinat_tableau_Tableau_class__ .sobj')
_class__ sage_combinat_tableau_Tableaux_n__ .sobj')

shouldn't be there having been replaced with new improved pickles with slightly more informative names (for example, _n_ --> _size_, _p_ --> _shape_ etc.). The pickle

_class__ sage_combinat_partition_PartitionTuples_nk__ .sobj

I agree is mine to fix but I am also not entirely convinced that the first three pickles are caused by this patch, that is the following pickles:

class__ sage_combinat_crystals_affine_AffineCrystalFromClassicalAndPromotion_with_category_element_class__ .sobj')
class__ sage_combinat_crystals_tensor_product_CrystalOfTableaux_with_category_element_class__ .sobj')
class__ sage_combinat_crystals_tensor_product_TensorProductOfCrystalsWithGenerators_with_category__ .sobj')

as I think that I might have also created new pickles for these in #9265. I am, of course, happy to rebuild them just in case.

Can you please confirm that the pickle_jar was updated as per the attachment for #9265. The mistake is quite probably mine as I assumed that the whole pickle jar would be replaced whereas if you just added in the new pickles then you would not have been aware that some of the old pickles needed to be deleted (although presumably it would not have been possible to unpickle them...??). If there is any documentation on updating the pickle jar please let me know.

Please advise.

Cheers,

Andrew

Last edited 19 months ago by andrew.mathas (previous) (diff)

comment:42 in reply to: ↑ 41 Changed 19 months ago by jdemeyer

Replying to andrew.mathas:

Can you please confirm that the pickle_jar was updated as per the attachment for #9265.

Yes, certainly it was updated.

comment:43 follow-up: Changed 19 months ago by jdemeyer

I don't quite understand what you're saying, since my failed test is only complaining about one pickle, namely

_class__sage_combinat_partition_PartitionTuples_nk__.sobj

comment:44 in reply to: ↑ 43 Changed 19 months ago by andrew.mathas

Sorry, my mistake: I was testing on 5.3.

A.

comment:45 follow-up: Changed 19 months ago by andrew.mathas

OK, I have fixed the long-test problem. With the pickle it seems to me that the only way to fix the problem is to replace the bad

PartitionTuples_nk

pickle in the pickle jar with a good one (and leave the other pickles untouched) as the underlying class has changed too much (vbraun posted a comment on #9265 suggesting that I should use register_unpickle_override instead but I tried experimenting with this and it doesn't seem to work).


Jeroen can you please confirm that you are are happy for me to do this.

comment:46 in reply to: ↑ 45 ; follow-up: Changed 19 months ago by jdemeyer

Replying to andrew.mathas:

Jeroen can you please confirm that you are are happy for me to do this.

Given the comments of Volker Braun and Simon King, I cannot be happy with this. No objects should be removed from the pickle jar.

comment:47 in reply to: ↑ 46 ; follow-up: Changed 19 months ago by nthiery

Replying to jdemeyer:

Replying to andrew.mathas:

Jeroen can you please confirm that you are are happy for me to do this.

Given the comments of Volker Braun and Simon King, I cannot be happy with this. No objects should be removed from the pickle jar.

Just my 2 cents: at this point, partition tuples are a rather peripheral feature. If anyone has saved some pickle containing one, most likely he is in the Sage-Combinat group. Well most likely it's Andrew actually. So I vote for not wasting Andrew's time and simply dropping backward compatibility in that particular situation. I am not taking much risk by volunteering to help whoever might have trouble with such an old pickle :-)

Of course, the official procedure would be to run a poll; if you insist, we can do that on Sage-Combinat devel.

comment:48 in reply to: ↑ 47 Changed 19 months ago by jdemeyer

Nicolas, I started a thread on sage-devel about the pickle jar.

comment:49 Changed 18 months ago by andrew.mathas

  • Status changed from needs_work to needs_review

Unpickling works now.

comment:50 Changed 18 months ago by tscrim

  • Status changed from needs_review to positive_review

Everything looks good to me (double checked the pickle jar and sage_object.pyx).

comment:51 follow-up: Changed 18 months ago by jdemeyer

  • Status changed from positive_review to needs_work

Removing all whitespace everywhere is a bad idea, don't do it as it will lead to merge conflicts (unless it was approved by the sage-combinat group, then I take back my words).

comment:52 in reply to: ↑ 51 Changed 18 months ago by andrew.mathas

Replying to jdemeyer:

Removing all whitespace everywhere is a bad idea, don't do it as it will lead to merge conflicts (unless it was approved by the sage-combinat group, then I take back my words).

Jeroen, I removed whitespaces added by the patch and then checked that the sage-combiat queue applied cleanly before pushing the patch both to the sage-combinat queue and back to trac. I did not remove all white space from the source files affected by this patch as, I agree, this would probably cause havoc with the queue. As all of the patches in the sage-combinat queue still apply cleanly I am putting this back to a positive review.

comment:53 Changed 18 months ago by andrew.mathas

  • Status changed from needs_work to positive_review

comment:54 Changed 18 months ago by jdemeyer

  • Merged in set to sage-5.5.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:55 Changed 18 months ago by jdemeyer

The new patch needs a proper commit message.

Changed 18 months ago by andrew.mathas

Adding proper commit message

Note: See TracTickets for help on using tickets.