bug in Partitions

[jhpalmieri]

Looks like there is a bug in Partitions. Partitions(n, max_slope=-1) should give the partitions of n with distinct parts, right?

sage: Partitions(2, max_slope=-1).list()
[[2]]
sage: Partitions(4, max_slope=-1).list()
[[4], [3, 1]]

But if you add the "length" keyword, it doesn't work anymore, at least not completely:

sage: Partitions(2, max_slope=-1, length=2).list()  # doesn't work
[[1, 1]]
sage: Partitions(4, max_slope=-1, length=2).list()  # works
[[3, 1]]
sage: Partitions(4, max_slope=-1, length=3).list()  # doesn't work
[[2, 1, 1]]

Depends on #12925

CC: @sagetrac-brunellus

Component: combinatorics

Keywords: partitions, days38

Author: Travis Scrimshaw

Reviewer: Benjamin Jones

Merged: sage-5.3.beta2

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

[tscrim]

comment:2

Fixed by making changes to IntergerListLex and not increasing algorithm's complexity. Fixed some other bugs in IntegerListLex and Partitions when bad input is given.

Note: most of the work on this patch was done during Sage Days 38.

[tscrim]

Changed keywords from partitions to partitions, days38

[tscrim]

Author: Travis Scrimshaw

[benjaminfjones]

comment:3

The code you've written looks good. I think you should also add a few doctests in EXAMPLES or TESTS where appropriate to demonstrate that the issue in this ticket it resolved.

[benjaminfjones]

Work Issues: add doctests

[benjaminfjones]

Reviewer: Benjamin Jones

[tscrim]

comment:4

Doctests have been added.

Thanks for reviewing.

[benjaminfjones]

Changed work issues from add doctests to none

[benjaminfjones]

comment:5

Changes look good and thanks for adding the doctests. You done some nice code cleanup too, which is great. Positive review pending make ptestlong.

[jdemeyer]

Dependencies: #12925

[jdemeyer]

comment:7

It fails a doctest:

sage -t  -force_lib devel/sage/sage/combinat/integer_vector.py
**********************************************************************
File "/release/merger/sage-5.2.beta1/devel/sage-main/sage/combinat/integer_vector.py", line 988:
    sage: IntegerVectors(3, 0, min_part=1).list()
Expected:
    []
Got:
    [[3]]
**********************************************************************

It also fails a test added by #12925:

sage -t  -force_lib devel/sage/sage/combinat/tutorial.py
**********************************************************************
File "/release/merger/sage-5.2.beta1/devel/sage-main/sage/combinat/tutorial.py", line 1635:
    sage: Partitions(2, max_slope=-1, length=2).list()
Expected:
    [[1, 1]]
Got:
    []
**********************************************************************

[tscrim]

comment:8

It now passes the test for integer_vector.py, however the test in #12925 is incorrect since the partition [1, 1] has a slope 0 > -1. (Or am I now responsible for correcting this because #12925 has been closed?)

[jdemeyer]

comment:9

Replying to @tscrim:

It now passes the test for integer_vector.py, however the test in #12925 is incorrect since the partition [1, 1] has a slope 0 > -1. (Or am I now responsible for correcting this because #12925 has been closed?)

I have reopened that ticket, so they can fix their test.

[nthiery]

comment:10

Replying to @jdemeyer:

Replying to @tscrim:

It now passes the test for integer_vector.py, however the test in #12925 is incorrect since the partition [1, 1] has a slope 0 > -1. (Or am I now responsible for correcting this because #12925 has been closed?)

I have reopened that ticket, so they can fix their test.

Have you read the text just above that doctest? It is precisely documenting this bug.

So, I am glad that you fixed that bug, but this ticket #6538 is responsible for updating the tutorial accordingly. Please merge back #12925! It's been delayed long enough.

[tscrim]

comment:11

Replying to @nthiery:

Replying to @jdemeyer:

Replying to @tscrim:

It now passes the test for integer_vector.py, however the test in #12925 is incorrect since the partition [1, 1] has a slope 0 > -1. (Or am I now responsible for correcting this because #12925 has been closed?)

I have reopened that ticket, so they can fix their test.

Have you read the text just above that doctest? It is precisely documenting this bug.

So, I am glad that you fixed that bug, but this ticket #6538 is responsible for updating the tutorial accordingly. Please merge back #12925! It's been delayed long enough.

Tutorial updated accordingly.

[nthiery]

comment:12

Tutorial updated accordingly.

Thanks! I am fine with this change.

Still, I am pretty sure that the underlying engine is still broken; if you can come up with an example illustrating that, please add it there!

Thanks,
Nicolas

[jdemeyer]

comment:13

Nicolas: it's not clear whether your comment should be interpreted as positive_review or needs_work? Could you change the ticket status to either of these two?

[nthiery]

comment:14

Replying to @jdemeyer:

Nicolas: it's not clear whether your comment should be interpreted as positive_review or needs_work? Could you change the ticket status to either of these two?

Sorry if I was unclear. Travis: I leave that decision to you. If you have an example, please add it. Otherwise you can put a positive review under hand.

Cheers,

[tscrim]

comment:15

I can't find an example right now. I've tried with max_slope, min_slope, inner, outer, max_length, min_length, and multiple combinations of them and could not get any wrong results.

[jdemeyer]

Attachment: trac_6538-partitions_max_slope-ts.patch.gz

Rebased to sage-5.3.beta1

[jdemeyer]

Merged: sage-5.3.beta2

[jhpalmieri]

comment:17

If you're still looking for something that gives the wrong answer, use parts_in:

sage: [len(p) for p in Partitions(10, length=6, parts_in=[1,2])]
[5, 6, 7, 8, 9, 10]
sage: Partitions(10, parts_in=[1,2]).cardinality() == Partitions(10, length=6, parts_in=[1,2]).cardinality()
True

Another ticket?

Edit: I guess this is #12278.)

[nthiery]

comment:18

Replying to @jhpalmieri:

If you're still looking for something that gives the wrong answer, use parts_in:

sage: [len(p) for p in Partitions(10, length=6, parts_in=[1,2])]
[5, 6, 7, 8, 9, 10]
sage: Partitions(10, parts_in=[1,2]).cardinality() == Partitions(10, length=6, parts_in=[1,2]).cardinality()
True

Another ticket?

Edit: I guess this is #12278.)

Yup: I copy pasted this example as a comment in #12278!

However, I was looking for an example giving wrong results while only using the IntegerListsLex engine (i.e. without parts_in). Thanks though :-)