Opened 8 years ago

# Partitions() is buggy — at Version 38

Reported by: Owned by: FerrisZorro FerrisZorro major sage-duplicate/invalid/wontfix combinatorics Partitions Jakob Kroeker, Anne Schilling N/A #17637

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

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

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

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

Partitions error

### comment:2 Changed 8 years ago by FerrisZorro

Owner: changed from z to FerrisZorro

### Changed 8 years ago by FerrisZorro

` #!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 8 years ago by Frédéric Chapoton

Authors: z v5.7 sage 5.7 sage5.7 sage-feature → sage-duplicate/invalid/wontfix f new → needs_review

### comment:4 Changed 8 years ago by Nathann Cohen

Status: needs_review → 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 8 years ago by Nathann Cohen

This being said this bug report is a real bug report `O_o`

### comment:6 Changed 8 years ago by Thierry Monteil

Component: number theory → combinatorics modified (diff) sage-duplicate/invalid/wontfix → sage-6.5 positive_review → needs_work sage5.7 Partitions() error → 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 follow-up:  13 Changed 8 years ago by Travis Scrimshaw

Milestone: sage-6.5 → sage-duplicate/invalid/wontfix needs_work → 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 8 years ago by Nathann Cohen

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 follow-up:  10 Changed 8 years ago by Travis Scrimshaw

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 8 years ago by Nathann Cohen

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 8 years ago by Travis Scrimshaw

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 8 years ago by FerrisZorro

OK, this ticket should be closed

### comment:13 in reply to:  7 Changed 8 years ago by Vincent Delecroix

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 `a-b` and not `b-a`. But hopefully, it is clear in the doctest.

### comment:14 Changed 8 years ago by Nathann Cohen

Authors: → Nathann Cohen → u/ncohen/17548 sage-duplicate/invalid/wontfix → sage-6.5

### comment:15 Changed 8 years ago by git

Commit: → 2edddbb2212b7c617576dcd35f1437fdaa26f834

Branch pushed to git repo; I updated commit sha1. New commits:

 ​87fb103 `17507: change error msg, add doctest` ​cd71e2b `Merge branch 'u/rws/minor_error_with_integral_n__' of trac.sagemath.org:sage into tmp` ​2edddbb `trac #17548: Partitions() involving min_slope argument is buggy`

### comment:16 Changed 8 years ago by git

Commit: 2edddbb2212b7c617576dcd35f1437fdaa26f834 → 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 8 years ago by Nathann Cohen

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:18 Changed 8 years ago by Nathann Cohen

Stopgaps: → #17637

Stopgap created at #17637.

Nathann

### comment:19 Changed 8 years ago by Travis Scrimshaw

It's not a wrong result, it's invalid input because it violates the assumptions.

### comment:20 Changed 8 years ago by Nathann Cohen

Branch: u/ncohen/17548 0919653ddd6b387f9fc7e409dac55dfc3a5128ce

(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 8 years ago by Nathann Cohen

Status: needs_review → needs_work

(there is nothing to review here)

### comment:22 Changed 8 years ago by Nathann Cohen

Authors: Nathann Cohen

### comment:23 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff) Partitions() involving min_slope argument is buggy → Partitions() is buggy

### comment:25 follow-up:  27 Changed 8 years ago by Vincent Delecroix

Hello,

Two bug-feature report.

1. Depending on the input, the floor is sometimes `0` and sometimes `1`:
```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]]
```
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]
```
Last edited 8 years ago by Vincent Delecroix (previous) (diff)

### comment:26 Changed 8 years ago by Nathann Cohen

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 ; follow-up:  29 Changed 8 years ago by Travis Scrimshaw

1. Depending on the input, the floor is sometimes `0` and sometimes `1`:
```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 non-trailing 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.

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

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:29 in reply to:  27 ; follow-up:  30 Changed 8 years ago by Jeroen Demeyer

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

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 ; follow-up:  32 Changed 8 years ago by Travis Scrimshaw

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 length-then-lex 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 8 years ago by Jakob Kroeker

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 ; follow-up:  34 Changed 8 years ago by Jeroen Demeyer

It does, but it is doing it by lex ordering, which is different than by length-then-lex 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 8 years ago by Jeroen Demeyer

Description: modified (diff) minor → major

### comment:34 in reply to:  32 Changed 8 years ago by William Stein

It does, but it is doing it by lex ordering, which is different than by length-then-lex 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 8 years ago by Jeroen Demeyer

Description: modified (diff)

### comment:36 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff)

### comment:37 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff)

### comment:38 Changed 8 years ago by Jeroen Demeyer

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