Implementation of PartitionTuple + some minor fixes to partition.py

[AndrewMathas]

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:

• Implementation of partition tuples
• number_of_partitions and friends and number_of_partitions

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.

2. 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 Use FLINT to compute the partition function #13199, which uses FLINT to implement a faster version of number_of_partitions, is merged into sage.

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

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

5. For the reasons given in RestrictedPartitions is very slow and a huge memory hog #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 misleading (outdated) docstring in partitions_restricted #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 Set factories #10194.

6. 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: attachment: trac_13072-tuples-of-partitions_am.patch

Depends on #9265
Depends on #11446

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: tuples of partitions

Author: Andrew Mathas

Reviewer: Travis Scrimshaw

Merged: sage-5.5.beta1

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

[AndrewMathas]

Changed work issues from Some category tests currently fails. to none

[AndrewMathas]

Changed dependencies from NA to #9265

[AndrewMathas]

comment:3

Should now apply cleanly to sage 5.2

[AndrewMathas]

comment:5

Apply trac_13072-tuples-of-partitions_am.patch

[AndrewMathas]

comment:7

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

[AndrewMathas]

comment:8

For the patchbot:

Apply trac_13072-tuples-of-partitions_am.patch

[tscrim]

Reviewer: Travis Scrimshaw

[AndrewMathas]

comment:11

For the patchbot:

Apply trac_13072-tuples-of-partitions_am.patch

[AndrewMathas]

comment:14

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

[jhpalmieri]

comment:16

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.

[AndrewMathas]

comment:19

For the patchbot:

Apply trac_13072-tuples-of-partitions_am.patch

[AndrewMathas]

comment:41

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

[jdemeyer]

comment:42

Replying to @AndrewAtLarge:

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

Yes, certainly it was updated.

[jdemeyer]

comment:43

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

[AndrewMathas]

comment:44

Sorry, my mistake: I was testing on 5.3.

A.

[AndrewMathas]

comment:45

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.

[jdemeyer]

comment:46

Replying to @AndrewAtLarge:

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.

[nthiery]

comment:47

Replying to @jdemeyer:

Replying to @AndrewAtLarge:

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.

[jdemeyer]

comment:48

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

[AndrewMathas]

comment:49

Unpickling works now.

[tscrim]

comment:50

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

[jdemeyer]

comment:51

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

[AndrewMathas]

comment:52

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.

[jdemeyer]

Merged: sage-5.5.beta1

[jdemeyer]

comment:55

The new patch needs a proper commit message.

[AndrewMathas]

Adding proper commit message

[AndrewMathas]

Attachment: trac_13072-tuples-of-partitions_am.patch.gz