Opened 8 years ago

Closed 5 years ago

Last modified 5 years ago

#6538 closed defect (fixed)

bug in Partitions

Reported by: jhpalmieri Owned by: mhansen
Priority: major Milestone: sage-5.3
Component: combinatorics Keywords: partitions, days38
Cc: brunellus Merged in: sage-5.3.beta2
Authors: Travis Scrimshaw Reviewers: Benjamin Jones
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12925 Stopgaps:

Description

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]]

Attachments (1)

trac_6538-partitions_max_slope-ts.patch (11.5 KB) - added by jdemeyer 5 years ago.
Rebased to sage-5.3.beta1

Download all attachments as: .zip

Change History (19)

comment:1 Changed 6 years ago by brunellus

  • Cc brunellus added
  • Report Upstream set to N/A

comment:2 Changed 6 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Keywords days38 added
  • Status changed from new to needs_review

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.

comment:3 Changed 6 years ago by benjaminfjones

  • Reviewers set to Benjamin Jones
  • Status changed from needs_review to needs_work
  • Work issues set to add doctests

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.

comment:4 Changed 5 years ago by tscrim

  • Status changed from needs_work to needs_review

Doctests have been added.

Thanks for reviewing.

comment:5 Changed 5 years ago by benjaminfjones

  • Status changed from needs_review to positive_review
  • Work issues add doctests deleted

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

comment:6 Changed 5 years ago by jdemeyer

  • Milestone changed from sage-5.1 to sage-5.2

comment:7 Changed 5 years ago by jdemeyer

  • Dependencies set to #12925
  • Status changed from positive_review to needs_work

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:
    []
**********************************************************************

comment:8 follow-up: Changed 5 years ago by tscrim

  • Status changed from needs_work to needs_review

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

comment:9 in reply to: ↑ 8 ; follow-up: Changed 5 years ago by 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.

comment:10 in reply to: ↑ 9 ; follow-up: Changed 5 years ago by 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.

comment:11 in reply to: ↑ 10 ; follow-up: Changed 5 years ago by tscrim

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.

comment:12 in reply to: ↑ 11 Changed 5 years ago by nthiery

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

comment:13 follow-up: Changed 5 years ago by 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?

comment:14 in reply to: ↑ 13 Changed 5 years ago by nthiery

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,

comment:15 Changed 5 years ago by tscrim

  • Status changed from needs_review to positive_review

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.

Changed 5 years ago by jdemeyer

Rebased to sage-5.3.beta1

comment:16 Changed 5 years ago by jdemeyer

  • Merged in set to sage-5.3.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:17 follow-up: Changed 5 years ago by 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.)

Last edited 5 years ago by jhpalmieri (previous) (diff)

comment:18 in reply to: ↑ 17 Changed 5 years ago by nthiery

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

Note: See TracTickets for help on using tickets.