Opened 6 years ago
Closed 6 years ago
#17548 closed defect (duplicate)
Partitions() is buggy
Reported by:  ferriszorro  Owned by:  ferriszorro 

Priority:  major  Milestone:  sageduplicate/invalid/wontfix 
Component:  combinatorics  Keywords:  Partitions 
Cc:  jakobkroeker, aschilling  Merged in:  
Authors:  Reviewers:  Jeroen Demeyer  
Report Upstream:  N/A  Work issues:  
Branch:  public/combinat/equal_min_max_slope_fix (Commits)  Commit:  44d1cfb45c137d7d8ac6eb481bf6145ec57c12e4 
Dependencies:  Stopgaps:  #17637, #17956 
Description (last modified by )
There are various bugs in Partitions
/Compositions
, especially when many constraints are combined:
sage: C = Partitions(10, min_part=2, max_slope=1) sage: [5,3,2] in C True sage: C.list() [[10], [8, 2], [7, 3], [6, 4]]
sage: C = Compositions(5, max_part=2, min_slope=1, inner=[2]) sage: [2,1,2] in C False sage: C.list() [[2, 1, 2]]
When slopes are equal, things often go wrong:
sage: C = Compositions(4, min_slope=0, max_slope=0) sage: [1,1,1,1] in C True sage: C.list() [[4], [2, 2]]
sage: C = Partitions(6, min_slope=1, max_slope=1) sage: [3,2,1] in C True sage: C.list() [[6]]
Contradictory length bounds still give results:
sage: C = Compositions(6, min_length=3, max_length=2) sage: [4,1,1] in C False sage: C.list()[0] [4, 1, 1]
sage: C = Compositions(3, max_length=2, inner=[1,1,1]) sage: [1,1,1] in C False sage: C.list() [[1, 1, 1]]
sage: C = Compositions(10, outer=[4], inner=[1,1]) sage: [4,6] in C False sage: C.list() [[4, 6], [3, 7], [2, 8], [1, 9]]
max_part
is not respected:
sage: C = Compositions(4, max_part=2, min_slope=1) sage: [1,3] in C False sage: C.list() [[1, 3]]
This is horribly wrong:
sage: Compositions(7, max_part=4, inner=[1], min_slope=1).list() [[3, 5], [1, 3, 4]]
The following command hangs:
sage: Compositions(4, inner=[2], outer=[2,2], min_slope=0).list() ...
Strange exception which really shouldn't be an exception:
sage: Compositions(10, inner=[1,1], max_slope=1) ... ValueError: floor does not satisfy the max slope condition
One possible fix is given by #17920.
Attachments (1)
Change History (52)
comment:1 Changed 6 years ago by
comment:2 Changed 6 years ago by
 Owner changed from z to ferriszorro
Changed 6 years ago by
#!diff # HG changeset patch # Date 1300721936 0 foo diff git a/bar b/bar  a/bar +++ b/bar @@ 1,2 +1,3 @@ baz quux +xyzzy
comment:3 Changed 6 years ago by
 Branch v5.7 deleted
 Dependencies sage 5.7 deleted
 Merged in sage5.7 deleted
 Milestone changed from sagefeature to sageduplicate/invalid/wontfix
 Reviewers f deleted
 Status changed from new to needs_review
comment:4 Changed 6 years ago by
 Status changed from needs_review to positive_review
Frédéric: the wontfix tickets should be set to 'positive review', otherwise Volker will not see them.
"Merry Christmas",
Nathann
comment:5 Changed 6 years ago by
This being said this bug report is a real bug report O_o
comment:6 Changed 6 years ago by
 Component changed from number theory to combinatorics
 Description modified (diff)
 Milestone changed from sageduplicate/invalid/wontfix to sage6.5
 Status changed from positive_review to needs_work
 Summary changed from sage5.7 Partitions() error to Partitions() involving min_slope argument is buggy
I was very puzzled when i saw this ticket, since my Turing tests were not able to conclude (unless we just reached the singularity). I propose to reopen the ticket since the report is correct.
By the way, i am not sure the following is a correct behaviour:
sage: P = Partitions(5, min_slope=2) sage: Q = Partitions(5) sage: Q[0] [5] sage: Q[0] in P False
comment:7 followup: ↓ 13 Changed 6 years ago by
 Milestone changed from sage6.5 to sageduplicate/invalid/wontfix
 Status changed from needs_work to needs_review
This is actually bad input: the slopes should be negative (to be useful for partitions). From the documentation of Partitions
:
 ``min_slope=k`` specifies that the partitions have slope at least `k`; the slope is the difference between successive parts.
The second input is actually correct, that is the only partition of 5 with a positive slope (provided you don't count trailing 0's, which is how Sage currently behaves). With that being said, the internal assumptions of IntegerListsLex
are also being broken with min_slope > max_slope == 0
, so it's no surprise bad data is being returned. So this should be a wontfix.
comment:8 Changed 6 years ago by
Does this also qualify as bad input ?
sage: list(Partitions(5,length=4,min_slope=0)) ... ValueError: [1, 1, 1, 2] is not a valid partition
Nathann
comment:9 followup: ↓ 10 Changed 6 years ago by
Currently yes. From the doc of IntegerListsLex
(which is the underlying class):
Note: Caveat: with the current implementation, the constraints should satisfy the following conditions: * The upper and lower bounds themselves should satisfy the slope constraints. * The maximal and minimal slopes values should not be equal. * The maximal and minimal part values should not be equal.
comment:10 in reply to: ↑ 9 Changed 6 years ago by
Currently yes. From the doc of
IntegerListsLex
(which is the underlying class):
Cool. So the strategy is to close as wontfix the attempts to change that because, after all, it is not a bug ?
Nathann
comment:11 Changed 6 years ago by
The other option would be to recycle this ticket to use for rewriting IntegerListsLex
, but in terms of historical documentation, I think this would best done on a new ticket.
comment:12 Changed 6 years ago by
OK, this ticket should be closed
comment:13 in reply to: ↑ 7 Changed 6 years ago by
Replying to tscrim:
This is actually bad input: the slopes should be negative (to be useful for partitions). From the documentation of
Partitions
: ``min_slope=k`` specifies that the partitions have slope at least `k`; the slope is the difference between successive parts.
This is confusing: the difference between a
and b
is ab
and not ba
. But hopefully, it is clear in the doctest.
comment:14 Changed 6 years ago by
 Branch set to u/ncohen/17548
 Milestone changed from sageduplicate/invalid/wontfix to sage6.5
comment:15 Changed 6 years ago by
 Commit set to 2edddbb2212b7c617576dcd35f1437fdaa26f834
comment:16 Changed 6 years ago by
 Commit changed from 2edddbb2212b7c617576dcd35f1437fdaa26f834 to 0919653ddd6b387f9fc7e409dac55dfc3a5128ce
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
0919653  trac #17548: Partitions() involving min_slope argument is buggy

comment:17 Changed 6 years ago by
Aahahahahah.
Okay, I spent the last 2h30 hours writing all the equations needed to ensure that there is a solution, and with all possibilities that there are I give up.
I will add a stopgap for this feature as it returns wrong results.
Nathann
comment:19 Changed 6 years ago by
It's not a wrong result, it's invalid input because it violates the assumptions.
comment:20 Changed 6 years ago by
 Branch u/ncohen/17548 deleted
 Commit 0919653ddd6b387f9fc7e409dac55dfc3a5128ce deleted
(the branch does not actually contain useful code. Switching this to needs_work
)
It's not a wrong result, it's invalid input because it violates the assumptions.
I was not able to write a patch that checks all assumptions and returns an exception in this case. If these assumptions are so complicated to check we cannot ask the users to check them for themselves before calling the function. Some of them are probably calling this function on bad input, and they are taking a big risk.
Nathann
comment:21 Changed 6 years ago by
 Status changed from needs_review to needs_work
(there is nothing to review here)
comment:22 Changed 6 years ago by
comment:23 Changed 6 years ago by
 Description modified (diff)
 Summary changed from Partitions() involving min_slope argument is buggy to Partitions() is buggy
comment:24 Changed 6 years ago by
 Cc jakobkroeker added
comment:25 followup: ↓ 27 Changed 6 years ago by
Hello,
Two bugfeature report.
 Depending on the input, the floor is sometimes
0
and sometimes1
:sage: IntegerListsLex(5, length=3).list() # ok: it is 0 [[5, 0, 0], [4, 1, 0], [4, 0, 1], ... [0, 2, 3], [0, 1, 4], [0, 0, 5]] sage: IntegerListsLex(5, length=3, max_slope=0).list() # ok: it is 0 [[5, 0, 0], [4, 1, 0], [3, 2, 0], [3, 1, 1], [2, 2, 1]] sage: IntegerListsLex(5, max_slope=0).list() # now it is 1 [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
 The iterator is sometimes completely wrong when the set is infinite:
sage: it = iter(IntegerListsLex(5)) sage: for _ in range(10): print it.next() [5] [4, 1] [4, 0, 1] [4, 0, 0, 1] [4, 0, 0, 0, 1] [4, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 0, 0, 0, 1]
comment:26 Changed 6 years ago by
This function should be replaced by smaller, more dedicated functions. Making it all fit in something so general makes it very hard to manage.
And wrong, too.
Nathann
comment:27 in reply to: ↑ 25 ; followup: ↓ 29 Changed 6 years ago by
Replying to vdelecroix:
 Depending on the input, the floor is sometimes
0
and sometimes1
:sage: IntegerListsLex(5, length=3).list() # ok: it is 0 [[5, 0, 0], [4, 1, 0], [4, 0, 1], ... [0, 2, 3], [0, 1, 4], [0, 0, 5]] sage: IntegerListsLex(5, length=3, max_slope=0).list() # ok: it is 0 [[5, 0, 0], [4, 1, 0], [3, 2, 0], [3, 1, 1], [2, 2, 1]] sage: IntegerListsLex(5, max_slope=0).list() # now it is 1 [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
This is not a bug because this has trailing 0's and there is no way to have a nontrailing 0 in the last output. See this part of the documentation:
Two valid integer lists are considered equivalent if they only differ by trailing zeroes. In this case, only the list with the least number of trailing zeroes will be produced.
It's subtle, but again, not a bug.
 The iterator is sometimes completely wrong when the set is infinite:
sage: it = iter(IntegerListsLex(5)) sage: for _ in range(10): print it.next() [5] [4, 1] [4, 0, 1] [4, 0, 0, 1] [4, 0, 0, 0, 1] [4, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 0, 0, 0, 1]
This is also not a bug because there are no other conditions on the lists and each of these are the next in lex ordering.
comment:28 Changed 6 years ago by
 Cc aschilling added
comment:29 in reply to: ↑ 27 ; followup: ↓ 30 Changed 6 years ago by
Replying to tscrim:
 The iterator is sometimes completely wrong when the set is infinite:
sage: it = iter(IntegerListsLex(5)) sage: for _ in range(10): print it.next() [5] [4, 1] [4, 0, 1] [4, 0, 0, 1] [4, 0, 0, 0, 1] [4, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 0, 0, 1] [4, 0, 0, 0, 0, 0, 0, 0, 0, 1]This is also not a bug because there are no other conditions on the lists and each of these are the next in lex ordering.
This is a bug! An iterator (finite or infinite) must eventually return every element of the set.
comment:30 in reply to: ↑ 29 ; followup: ↓ 32 Changed 6 years ago by
Replying to jdemeyer:
This is also not a bug because there are no other conditions on the lists and each of these are the next in lex ordering.
This is a bug! An iterator (finite or infinite) must eventually return every element of the set.
It does, but it is doing it by lex ordering, which is different than by lengththenlex ordering. Its the same as doing a Cartesian product of {1,2} x NN
and getting [1, 0]
, [1, 1]
, [1, 2]
, ... Is that a bug to you then too?
comment:31 Changed 6 years ago by
Is that a bug to you then too?
formally not, but the design is unfortunate. I suggest to change the behaviour.
Jakob
comment:32 in reply to: ↑ 30 ; followup: ↓ 34 Changed 6 years ago by
Replying to tscrim:
It does, but it is doing it by lex ordering, which is different than by lengththenlex ordering.
OK, listing all elements in lex ordering might not be possible. Fine, then raise an exception instead of returning a wrong answer.
Its the same as doing a Cartesian product of
{1,2} x NN
and getting[1, 0]
,[1, 1]
,[1, 2]
, ... Is that a bug to you then too?
Of course that's a bug.
comment:33 Changed 6 years ago by
 Description modified (diff)
 Priority changed from minor to major
comment:34 in reply to: ↑ 32 Changed 6 years ago by
Replying to jdemeyer:
Replying to tscrim:
It does, but it is doing it by lex ordering, which is different than by lengththenlex ordering.
OK, listing all elements in lex ordering might not be possible. Fine, then raise an exception instead of returning a wrong answer.
Its the same as doing a Cartesian product of
{1,2} x NN
and getting[1, 0]
,[1, 1]
,[1, 2]
, ... Is that a bug to you then too?Of course that's a bug.
+1  It is a reasonable basic principle that when iterating over a set S, for every x in S the iterator must eventually return x, as (Jereon said above). If this is impossible due to constraints on the order of iteration, there should be an error...
comment:35 Changed 6 years ago by
 Description modified (diff)
comment:36 Changed 6 years ago by
 Description modified (diff)
comment:37 Changed 6 years ago by
 Description modified (diff)
comment:38 Changed 6 years ago by
 Description modified (diff)
comment:39 Changed 6 years ago by
 Description modified (diff)
comment:40 Changed 6 years ago by
 Description modified (diff)
comment:41 Changed 6 years ago by
 Description modified (diff)
comment:42 Changed 6 years ago by
 Description modified (diff)
comment:43 Changed 6 years ago by
 Stopgaps changed from #17637 to #17637, #17956
comment:44 Changed 6 years ago by
 Description modified (diff)
comment:45 followups: ↓ 47 ↓ 48 Changed 6 years ago by
 Branch set to public/combinat/equal_min_max_slope_fix
 Commit set to 52db42b01c1b86c752652a09533e50dd0d899ab3
The branch I've attached fixes the length bounds and when min_slope == max_slope
. However these violate the internal assumptions:
sage: C = Compositions(4, max_part=2, min_slope=1) sage: Compositions(7, max_part=4, inner=[1], min_slope=1)
since the ceiling defaults to max_part
, which is always 2/4 and has a slope of 0 and violates the min_slope
condition (i.e., the ceiling must be increasing).
Also FTR, the last one in the description is the error message that was wanted (precisely because it violates the conditions).
comment:46 Changed 6 years ago by
 Commit changed from 52db42b01c1b86c752652a09533e50dd0d899ab3 to 44d1cfb45c137d7d8ac6eb481bf6145ec57c12e4
Branch pushed to git repo; I updated commit sha1. New commits:
44d1cfb  Fixes for min_slope == max_slope and length conditions.

comment:47 in reply to: ↑ 45 Changed 6 years ago by
Replying to tscrim:
the last one in the description is the error message that was wanted (precisely because it violates the conditions).
My point with the last one is that it should simply be allowed input. There is no fundamental reason why
sage: Compositions(10, inner=[1,1], max_slope=1)
shouldn't "just work".
comment:48 in reply to: ↑ 45 ; followup: ↓ 49 Changed 6 years ago by
Replying to tscrim:
These violate the internal assumptions
Then you really should add checks in the code raising an exception if the condition is not satisfied. If you do add such checks, make sure to add them to IntegerListsLex
and not the Partitions
/Compositions
frontends.
But even better would be to just allow such input.
comment:49 in reply to: ↑ 48 Changed 6 years ago by
Replying to jdemeyer:
Replying to tscrim:
These violate the internal assumptions
Then you really should add checks in the code raising an exception if the condition is not satisfied. If you do add such checks, make sure to add them to
IntegerListsLex
and not thePartitions
/Compositions
frontends.But even better would be to just allow such input.
In principle, all these bugs should now be fixed with #17979. Please check!
comment:50 Changed 6 years ago by
 Milestone changed from sage6.5 to sageduplicate/invalid/wontfix
 Reviewers set to Jeroen Demeyer
 Status changed from needs_work to positive_review
comment:51 Changed 6 years ago by
 Resolution set to duplicate
 Status changed from positive_review to closed
Partitions error