Opened 8 years ago

Last modified 8 years ago

#13072 closed enhancement

Implementation of PartitionTuple + some minor fixes to partition.py — at Version 20

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:
Authors: Andrew Mathas Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #9265 Stopgaps:

Description (last modified by andrew.mathas)

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-tableaux-am.patch

Change History (20)

comment:1 Changed 8 years ago by andrew.mathas

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

comment:2 Changed 8 years ago by andrew.mathas

  • Work issues Some category tests currently fails. deleted

comment:3 Changed 8 years 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 8 years ago by andrew.mathas

  • Description modified (diff)

comment:5 Changed 8 years ago by andrew.mathas

Apply trac_13072-tuples-of-partitions_am.patch

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

comment:6 Changed 8 years ago by andrew.mathas

  • Description modified (diff)

comment:7 Changed 8 years 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 8 years ago by andrew.mathas

For the patchbot:

Apply trac_13072-tuples-of-partitions_am.patch

comment:9 Changed 8 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

comment:10 Changed 8 years ago by andrew.mathas

  • Description modified (diff)

comment:11 Changed 8 years ago by andrew.mathas

For the patchbot:

Apply trac_13072-tuples-of-partitions_am.patch

comment:12 Changed 8 years ago by andrew.mathas

  • Description modified (diff)

comment:13 Changed 8 years ago by andrew.mathas

  • Description modified (diff)

comment:14 Changed 8 years 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 8 years ago by andrew.mathas

  • Description modified (diff)

comment:16 Changed 8 years 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 8 years ago by jhpalmieri (previous) (diff)

comment:17 Changed 8 years ago by andrew.mathas

  • Description modified (diff)

comment:18 Changed 8 years ago by andrew.mathas

  • Description modified (diff)

comment:19 Changed 8 years ago by andrew.mathas

For the patchbot:

Apply trac_13072-tuples-of-partitions_am.patch

comment:20 Changed 8 years ago by andrew.mathas

  • Description modified (diff)
Note: See TracTickets for help on using tickets.