[with patch, positive review] New class IntegerListLex for generating integer lists => much improved partition iterators

[nthiery]

IntegerListsLex? refactoring, and application to Partitions

• Reworked the integer lists lexicographic generator into a full featured combinatorial class IntegerListsLex?
• support for n in a set (or any iterable I implementing n in I)

Applications to Partitions:

• Systematic use of IntegerListsLex? to get constant amortized time iterators (huge efficiency improvement).
• This includes PartitionsGreatestEQ and PartitionsGreatestLE which were previously implemented in GAP. This was inefficient due to the communication overhead, and not using an iterator. (backward compatible unpickling)
• Implements horizontal_border_strip.

[nthiery]

Reworked the integer lists lexicographic generator into a full featured combinatorial class IntegerListsLex? Use it systematically in Partitions to get constant amortized time iterators. Also implements horizontal_border_strip.

Note: the attached patch does not contain the commit messages!

[saliola]

Replying to nthiery:

See the title. Patch integer_lists_lex-nt in development in sage-combinat.

Note: this patch depends on #4371 and #5255.

[mhansen]

I've added a patch which adds some doctests, adds a warning when min_part=0 is passed to partitions, and changed the default implementation of count to use Integers so that we don't have to reimplemented in IntegerListsLex?

Assuming someone okay's my changes, I think both patches are good to go in.

[hivert]

Replying to mhansen: It's ok for me ! The warning is a good idea. Go ahead.

[mabshoff]

This patch breaks the pickle jar which according to Mike is no surprise:

sage -t -long "devel/sage/sage/structure/sage_object.pyx"   
**********************************************************************
File "/scratch/mabshoff/sage-3.3.rc1/devel/sage/sage/structure/sage_object.pyx", line 682:
    sage: sage.structure.sage_object.unpickle_all(std)
Expected:
    doctest:...: DeprecationWarning: Your data is stored in an old format. Please use the save() function to store your data in a more recent format.
    doctest:...: DeprecationWarning: RQDF is deprecated; use RealField(212) instead.
    Successfully unpickled ... objects.
    Failed to unpickle 0 objects.
Got:
    doctest:1172: DeprecationWarning: Your data is stored in an old format. Please use the save() function to store your data in a more recent format.
    doctest:1172: DeprecationWarning: RQDF is deprecated; use RealField(212) instead.
    ** failed:  _class__sage_combinat_partition_PartitionsGreatestEQ_nk__.sobj
    ** failed:  _class__sage_combinat_partition_Partitions_constraints__.sobj
    ** failed:  _class__sage_combinat_partition_PartitionsGreatestLE_nk__.sobj
    Failed:
    _class__sage_combinat_partition_PartitionsGreatestEQ_nk__.sobj
    _class__sage_combinat_partition_Partitions_constraints__.sobj
    _class__sage_combinat_partition_PartitionsGreatestLE_nk__.sobj
    Successfully unpickled 445 objects.
    Failed to unpickle 3 objects.
**********************************************************************

We need to make a call if we are going to break this pickles or not. Other than that there were no doctesting issues.

Cheers,

Michael

[nthiery]

Replying to mhansen:

I've added a patch which adds some doctests, adds a warning when min_part=0 is passed to partitions,

Thanks!

and changed the default implementation of count to use Integers

Good.

so that we don't have to reimplemented in IntegerListsLex?

We still do! Sorry, I did not comment on this in the code, but the implementation of count differs from the default one from CombinatorialClass?, as it bypasses the call to _element_constructor_!

[nthiery]

Replying to mabshoff:

This patch breaks the pickle jar which according to Mike is no surprise:

Indeed no surprise.

We need to make a call if we are going to break this pickles or not. Other than that there were no doctesting issues.

I would tend to break the pickles indeed, unless someone cries very loud for this.

Cheers,

Nicolas

[mabshoff]

I am cleaning up the 3.3 milestone. If a patch with positive review is put up to this ticket on time it might make it into 3.3.

Cheers,

Michael

[nthiery]

Updated patch:

• Now handles pickles of PartitionsGreatestEQ and PartitionsGreatestLE from sage <= 3.4.1.
• Rebased against 3.4 (and sphinx)

[nthiery]

I should mention: only the last patch is needed; it integrates the previous ones

[hivert]

Dear Nicolas,

I should mention: only the last patch is needed; it integrates the previous ones

The patch looks good to me. However, though I'm not 100% sure I launched the correct check, it seems that one of the old pickle is still broken:

sage: std = os.environ['SAGE_DATA'] + '/extcode/pickle_jar/pickle_jar.tar.bz2'
sage: sage.structure.sage_object.unpickle_all(std)
** failed:  _class__sage_combinat_partition_Partitions_constraints__.sobj
/usr/local/sage/sage/local/lib/python2.5/site-packages/IPython/iplib.py:2073: DeprecationWarning: RQDF is deprecated; use RealField(212) instead.
  exec code_obj in self.user_global_ns, self.user_ns
Failed:
_class__sage_combinat_partition_Partitions_constraints__.sobj
Successfully unpickled 486 objects.
Failed to unpickle 1 objects.

Am I doing something wrong ?

Cheers,

Florent

[hivert]

Fix for the remaining broken pickle + tests for the other one.

[hivert]

Dear All,

The patch looks good to me. However, though I'm not 100% sure I launched the correct check, it seems that one of the old pickle is still broken:

I added a review patch which should fix this remaining pickle problem. If someone reread it I'm ready to give a positive review.

Florent

[nthiery]

Thanks Florent for the fix. I had overlooked this pickle. Oh, and thanks for pointing out how one can test backward compatibility unpickles :-)

I tried the patch on my machine and it looks and works fine.

So, I allow myself to set the positive review flag on behalf of Florent!

I also lifted the priority to major, since this gives a large (memory) efficiency gain.

[hivert]

If its still possible, I'd rather see this integrated in 3.4.1, this allows for #5308 being integrated as soon as possible.

Florent

[mabshoff]

Merged

• integer_lists_lex-4549-submitted.patch
• integer_lists_lex-4549-review.patch

in Sage 3.4.1.rc0.

Cheers,

Michael