Opened 5 years ago
Last modified 5 years ago
#17979 closed defect
Reimplementation of IntegerListsLex — at Version 285
Reported by:  aschilling  Owned by:  

Priority:  blocker  Milestone:  sage6.6 
Component:  combinatorics  Keywords:  days64 
Cc:  nthiery, tscrim, ncohen, vdelecroix, bgillespie  Merged in:  
Authors:  Bryan Gillespie, Anne Schilling, Nicolas M. Thiery  Reviewers:  Nathann Cohen, Jeroen Demeyer, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  public/ticket/17979 (Commits)  Commit:  a939fd59bfcf043bce3c9a61ae072337961873da 
Dependencies:  Stopgaps: 
Description (last modified by )
As documented in #17548, #17956, #17920, there are several bugs in IntegerListsLex which also have implications for !Partitions and !Compositions. This branch reimplements IntegerListsLex.
See also #18055 and #18056 for followups.
TODO:
 Forward smoothing of ceiling and floor for better detection of infinite parts
Change History (285)
comment:1 Changed 5 years ago by
 Priority changed from major to blocker
comment:2 Changed 5 years ago by
comment:3 followup: ↓ 6 Changed 5 years ago by
Some people at Sage Days 64 are planning to work on this. Give us some time!
comment:4 Changed 5 years ago by
 Description modified (diff)
 Keywords days64 added
comment:5 Changed 5 years ago by
 Cc ncohen added
comment:6 in reply to: ↑ 3 ; followups: ↓ 8 ↓ 9 Changed 5 years ago by
comment:7 Changed 5 years ago by
Another note: it would be very good if you didn't have any strange conditions on which input is allowed. Mathematically, all combinations of input constraints make sense, so they should all be allowed.
comment:8 in reply to: ↑ 6 ; followups: ↓ 10 ↓ 45 Changed 5 years ago by
Hi Jeroen,
Replying to jdemeyer:
Replying to aschilling:
Give us some time!
It was a question, not an attack...
Oops, sorry, I guess there just has been a bit too much turmoil on the topic lately :) We just got uncomfortable with the "blocker", for at this stage it's hard to predict how much time this will take (Sage days are great for sprints, but you get easily sidetracked). Any idea when the next release of Sage is likely to come out?
In any cases, here is the current plan. We are having a sprint here to work on reimplementing IntegerListLex? from scratch. We believe it's possible to have a correct iteration algorithm, with complexity roughly linear in the output in the common use cases, that will detect and report any invalid input. There will be situations where computing the next element may run forever. In those cases, we will report beforehand a warning, which the user will be able to silence by signing a waiver after having read the fine prints in the documentation.
If we can use the occasion to get generalizations for free, we will do so; but otherwise we will focus on getting the existing features right. Similarly, we will try to design the algorithm to potentially support cythonization / parallelism / implementation as a standalone C++ library, but postpone those for later.
And we will reuse everything we can from your work!
Cheers,
Nicolas
comment:9 in reply to: ↑ 6 Changed 5 years ago by
Replying to jdemeyer:
Replying to aschilling:
Give us some time!
It was a question, not an attack...
Yes, no problem :) We are discussing the algorithms, so once we are convinced it will all work, there is a group of people here that will try to implement it.
comment:10 in reply to: ↑ 8 Changed 5 years ago by
Replying to nthiery:
We just got uncomfortable with the "blocker", for at this stage it's hard to predict how much time this will take
I made it a blocker not because of this specific ticket, but because something needs to be done: either a proper stopgap needs to be put back (which is essentially reverting #17898), or we switch to my correctbutslow polyhedron implementation, or this ticket needs to be finished.
comment:12 followup: ↓ 13 Changed 5 years ago by
 Cc vdelecroix added
comment:13 in reply to: ↑ 12 Changed 5 years ago by
Brief update from Sage Days 64: Bryan Gillespie implemented the algorithm we discussed! The code runs and all doc tests pass, including all the previous failures that Jeroen pointed out! The code is still about 10 times slower than the current implementation of IntegerListsLex?, but at least appears to have no bugs and no restrictions any longer on the parameters. We will try to work on making it more efficient.
comment:14 Changed 5 years ago by
Only twice slower now that it uses +inf instead of infinity. infinity really needs to be optimized!
comment:15 followup: ↓ 102 Changed 5 years ago by
I would be 1 to using float('inf')
just because it's faster. The Right Thing to do is to use Sage's Infinity
and optimize that.
comment:16 followup: ↓ 17 Changed 5 years ago by
Where is the code...?
Given that rc0 has been released, we need to decide on a strategy to fix IntegerListsLex
(either this ticket or a "plan B" if this ticket doesn't get finished).
comment:17 in reply to: ↑ 16 ; followup: ↓ 18 Changed 5 years ago by
Replying to jdemeyer:
Where is the code...?
Given that rc0 has been released, we need to decide on a strategy to fix
IntegerListsLex
(either this ticket or a "plan B" if this ticket doesn't get finished).
I can push the code, but currently the interface with partitions and compositions is still broken and a lot of functions (like next, first etc ) that are also used in integer_vector need to be deprecated. That has not been done yet.
Best,
Anne
comment:18 in reply to: ↑ 17 Changed 5 years ago by
Replying to aschilling:
I can push the code, but currently the interface with partitions and compositions is still broken
How come? I didn't have this issue with #17920.
comment:19 Changed 5 years ago by
 Branch set to public/ticket/17979
 Commit set to fb341ea0e6edf9f5958d9d911023c5be201ec9b2
Last 10 new commits:
3793cc9  17989: added docs for min_part and max_part

b61fc8c  17979 added waiver

afffd99  Merge branch 'develop' into public/ticket/17979

0356dc1  Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into public/ticket/17979

8b9f643  17979 Small changes to IntegerVector and Partition related to floor and ceiling functions in IntegerListsLex

79d0a65  17979 fixed input in integer_matrices

ee0269f  Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into public/ticket/17979

dc26f9d  17979: update integer vectors w.r.t. the new IntegerListLex, using inheritance to reduce the amount of code + cleanup

7333951  17979 fixed doc tests in integer_list_old

fb341ea  Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into ticket/17979

comment:20 Changed 5 years ago by
 Commit changed from fb341ea0e6edf9f5958d9d911023c5be201ec9b2 to a3244c09abcea9c9d25fe5043d340692096ccd90
comment:21 Changed 5 years ago by
 Commit changed from a3244c09abcea9c9d25fe5043d340692096ccd90 to e91350397834e04c939029b6677a51da25231194
comment:22 Changed 5 years ago by
 Commit changed from e91350397834e04c939029b6677a51da25231194 to 865a2af4abb9c5a677990c54e435c5d6861f3cf5
comment:23 Changed 5 years ago by
 Commit changed from 865a2af4abb9c5a677990c54e435c5d6861f3cf5 to 6153cf8d39dc23cb41a3d0c2ea66ba5dc3abd2c0
comment:24 Changed 5 years ago by
Here are the failures I got upon make ptestlong:
sage t long src/sage/doctest/test.py # 1 doctest failed sage t long src/sage/tests/interrupt.pyx # 1 doctest failed sage t long src/sage/parallel/decorate.py # 1 doctest failed sage t long src/sage/schemes/elliptic_curves/lseries_ell.py # Timed out sage t long src/sage/modular/arithgroup/arithgroup_perm.py # Timed out sage t long src/sage/sets/set_from_iterator.py # 3 doctests failed sage t long src/sage/combinat/words/words.py # 5 doctests failed sage t long src/sage/algebras/weyl_algebra.py # 3 doctests failed
The last three are diagnosed (the new IntegerListLex? was missing the feature of accepting an iterable for n) and is being fixed. The rest look more like unrelated failures.
comment:25 Changed 5 years ago by
 Status changed from new to needs_review
 Work issues set to support n in an iterable
comment:26 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:27 followups: ↓ 28 ↓ 54 ↓ 55 ↓ 65 Changed 5 years ago by
Helloooooooooooo,
Here are some comments (mostly doc) about the current branch
 About
An integer list is a list l of nonnegative integers, its parts. The length of l is the number of its parts Note Two valid integer lists are considered equivalent if they only differ by trailing zeroes.
Unless the length of a list is the number of its nonzero entries, it does not seem to be properly defined.
The constraints on the lists are as follows:
 in what follows you use a variablel
often (probably one of the lists): could you say so explicitly?
 It seems that currently the method accepts input that does not satisfy the constraints that you list, i.e.:
sage: IntegerListsLex(min_n=4) Integer lists of sum between 4 and 0 satisfying certain constraints sage: list(IntegerListsLex(min_n=4)) []
Should they really be considered as 'constraints', if the code accepts them and returns sensible output (i.e. empty sets)? When I read those lines, I expected the code to raise a
ValueError
exception on them.
Lower and upper bounds
: the text about constant values for floor/ceiling belongs to the INPUT block.
waiver
 the description ofwaiver
in the INPUT block is very mysterious. If it is only meant for internal purposes, could you say so in its description?
Next we obtain all lists of sum 4 and length 4 such that l[i] <= i:
 missing backticks at the end.
 Comparative timings: should they really appear in the function's documentation? To me the trac ticket is the right place for that.
 There are two 'TESTS' sections
self.warning = False # warning for dangerous (but possibly valid) usage
 could say what this flag does?
 the INPUT blocks says that
n
can be a list. Could you add there an explanation of what it means?
 About the message
warn("""When the user specifies a method, then (s)he is responsible that the algorithm will not hang. Also note that the specified function should start at 0 rather than 1. Before trac#17979 the indexing was ambiguous and sometimes started at 1.""")
From time to time we receive bug reports on sagedevel or sagesupport in which the users beg us to forgive them in case what they think might be a bug could actually be their mistake. Could this message be changed to something more
technical
? Something like `you defined ceiling=[...] to be a function, and we cannot swear that this call will not hang`?
 About the copyright header: I never saw any patch remove the name of other persons in a copyright header. Don't know what the policy is.
# Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>, # Copyright (C) 2012 Travis Scrimshaw <tscrim@ucdavis.edu> +# Copyright (C) 2015 Bryan Gillespie <Brg008@gmail.com>,
Thanks,
Nathann
comment:28 in reply to: ↑ 27 ; followup: ↓ 29 Changed 5 years ago by
Replying to ncohen:
 About the copyright header: I never saw any patch remove the name of other persons in a copyright header.
That's not really true, there are many tickets which just remove whole modules, including the copyright header. If the whole module is completely rewritten (but only then), it's valid to remove the copyright header.
comment:29 in reply to: ↑ 28 Changed 5 years ago by
That's not really true, there are many tickets which just remove whole modules, including the copyright header. If the whole module is completely rewritten (but only then), it's valid to remove the copyright header.
Okay, no prob then.
comment:30 Changed 5 years ago by
I would prefer min_sum
and max_sum
instead of min_n
and max_n
(n
is just a letter and doesn't mean anything). I also think the defaults should be 0
and Infinity
instead of 0
and 0
.
In this case, you probably do not need support for iteratable n
since (AFAIK) all cases of iterables are really intervals and can be specified with min_sum
and max_sum
instead.
comment:31 Changed 5 years ago by
Replace
list(IntegerListsLex(4, length = 4, ceiling = lambda i: i, waiver=True))
by
list(IntegerListsLex(4, length=4, ceiling=lambda i: i, waiver=True))
and the same for similar places.
comment:32 Changed 5 years ago by
There should be empty lines between the bullet points in the INPUT
block.
comment:33 followup: ↓ 163 Changed 5 years ago by
The heading should be formatted like http://www.sagemath.org/doc/developer/coding_basics.html#headingsofsagelibrarycodefiles (in particular, it's bad to mention the GPL without version number).
comment:34 followup: ↓ 68 Changed 5 years ago by
Why do you want to supporting floor
and ceiling
being a number? We already have min_part
and max_part
for that.
comment:35 Changed 5 years ago by
Is this still true?
This is a generic low level tool. The interface has been designed with efficiency in mind. It is subject to incompatible changes in the future. More user friendly interfaces are provided by high level tools like :class:`Partitions` or :class:`Compositions`.
comment:36 followup: ↓ 69 Changed 5 years ago by
Is this really true?
Before trac#17979 the indexing was ambiguous and sometimes started at 1.
comment:37 Changed 5 years ago by
Use newstyle doctest formatting: indent with ....:
instead of ...
comment:38 Changed 5 years ago by
I agree with Nathann that the stuff about timings should be removed.
comment:39 followups: ↓ 70 ↓ 133 Changed 5 years ago by
There is still this bug:
sage: it = iter(IntegerListsLex(4)) sage: for _ in range(20): print next(it) [4] [3, 1] [3, 0, 1] [3, 0, 0, 1] [3, 0, 0, 0, 1] [3, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
It seems that [1,3]
will never appear in the output!
comment:40 followups: ↓ 43 ↓ 88 Changed 5 years ago by
This takes forever, even though the list trivially contains just one element:
sage: IntegerListsLex(10^100, max_length=1).list()
comment:41 followup: ↓ 176 Changed 5 years ago by
Some implementations might not use keyword arguments for length
, so the min_n
and max_n
arguments (preferably renamed to min_sum
and max_sum
) should be moved towards the end of the argument list.
comment:42 Changed 5 years ago by
I would prefer negative values of min_part
, max_part
to raise a NotImplementedError
since the question makes sense mathematically, it's just not implemented.
comment:43 in reply to: ↑ 40 Changed 5 years ago by
comment:44 Changed 5 years ago by
Note that this example is instant with #17920:
sage: IntegerLists(10^100, max_length=1).list()
comment:45 in reply to: ↑ 8 ; followups: ↓ 97 ↓ 154 Changed 5 years ago by
comment:46 followup: ↓ 89 Changed 5 years ago by
Remove
from sage.structure.list_clone import ClonableArray from sage.rings.integer import Integer
comment:47 Changed 5 years ago by
This comment is silly:
In the following example, the floor conditions do not satisfy the slope conditions since the floor for the third part is also 3. The algorithm will nonetheless give the correct result::
comment:48 followup: ↓ 71 Changed 5 years ago by
I dislike the fact that the warning shows even in cases where the output is obviously finite:
sage: IntegerListsLex(5, ceiling=lambda i:i, length=5) /usr/local/src/sageconfig/local/lib/python2.7/sitepackages/sage/combinat/integer_list.py:606: UserWarning: When the user specifies a method, then (s)he is responsible that the algorithm will not hang. Also note that the specified function should start at 0 rather than 1. Before trac#17979 the indexing was ambiguous and sometimes started at 1. Before trac#17979 the indexing was ambiguous and sometimes started at 1.""") Integer lists of sum 5 satisfying certain constraints
Also note that the formatting of the warning is not quite right.
comment:49 Changed 5 years ago by
Replace
raise(Exception("message"))
by
raise Exception("message")
comment:50 followup: ↓ 52 Changed 5 years ago by
It's a pity that this code is sometimes very fast and sometimes very slow depending on the input. My approach #17920 was slower, but in a more "uniform" way, never so slow that it was unusable.
comment:51 followup: ↓ 95 Changed 5 years ago by
What is IntegerVectors
and why is it not an alias of IntegerListsLex
?
comment:52 in reply to: ↑ 50 ; followup: ↓ 63 Changed 5 years ago by
It's a pity that this code is sometimes very fast and sometimes very slow depending on the input. My approach #17920 was slower, but in a more "uniform" way, never so slow that it was unusable.
This is probably because it is hard to check whether the list that you are trying to build can be "extended" into a list that satisfies all conditions.
I have not gone through the code yet, but it seems that the strategy is to try all possible choices for the first integer, then try all possible choices for the second (etc.) each time checking the constraints on what has already been decided (but not guessing anything about the future)
Thus, and still assuming that I did not misunderstand anything, the following set (which contains only one element) will only be returned after around 2^n
operations:
sage: n=20; IntegerLists(n, length=n,max_part=1).list()
Certainly some "cuts" can be added to detect when a partial sequence cannot be extended.
Nathann
comment:53 followup: ↓ 101 Changed 5 years ago by
Please use Infinity
instead of infinity
such that, if we ever use Infinity
from sage.rings.infinity
, we don't need to change infinity
to Infinity
everywhere.
comment:54 in reply to: ↑ 27 Changed 5 years ago by
Replying to ncohen:
 It seems that currently the method accepts input that does not satisfy the constraints that you list, i.e.:
sage: IntegerListsLex(min_n=4) Integer lists of sum between 4 and 0 satisfying certain constraints sage: list(IntegerListsLex(min_n=4)) []Should they really be considered as 'constraints', if the code accepts them and returns sensible output (i.e. empty sets)?
I think that returning the empty set is the right answer here. As long as the question makes sense mathematically, there should be an answer, not an exception.
The only thing which can be a ValueError
exception would be a negative length, since that doesn't even have a mathematical meaning. But I know from #17920 that some Partitions
code gives a negative minimum length, so a negative value for min_length
should just be treated as 0.
comment:55 in reply to: ↑ 27 Changed 5 years ago by
Replying to ncohen:
 the INPUT blocks says that
n
can be a list. Could you add there an explanation of what it means?
Alternatively, remove support for n
being a list. It's nowhere used in Sage. The old code "supported" it but it was never documented.
comment:56 followups: ↓ 73 ↓ 106 Changed 5 years ago by
This limitation should be mentioned somewhere in the docs:
sage: IntegerListsLex(length=2, max_n=Infinity, ceiling=[Infinity, 0], floor=[0,1]).list() Traceback (most recent call last): ... ValueError: infinite upper bound for values of m
(this is another example which "just works" with #17920).
comment:57 Changed 5 years ago by
There are a lot of TODO
items in the code and #commented out code which should be cleaned up.
comment:58 Changed 5 years ago by
Errors like these should be TypeError
instead of ValueError
:
raise(ValueError("unable to parse value of min_part"))
comment:59 followup: ↓ 77 Changed 5 years ago by
What's the point of setting self.floor_type
if you don't use it?
comment:60 Changed 5 years ago by
This is not a tricky question but still takes forever:
sage: IntegerLists(1, min_part=0, max_part=0).list()
comment:61 Changed 5 years ago by
Use Infinity
here:
self.floor_limit_start = float('+inf')
comment:62 followup: ↓ 64 Changed 5 years ago by
 Cc bgillespie added
Thanks for the thorough commentsNicolas, Anne and I have been working on this ticket persistently for just the last week at Sage Days 64, and we didn't have the time to polish every facet yet. I'll do my best to answer your questions about the algorithm and some of the design choices.
comment:63 in reply to: ↑ 52 Changed 5 years ago by
Replying to ncohen:
It's a pity that this code is sometimes very fast and sometimes very slow depending on the input. My approach #17920 was slower, but in a more "uniform" way, never so slow that it was unusable.
This is probably because it is hard to check whether the list that you are trying to build can be "extended" into a list that satisfies all conditions.
I have not gone through the code yet, but it seems that the strategy is to try all possible choices for the first integer, then try all possible choices for the second (etc.) each time checking the constraints on what has already been decided (but not guessing anything about the future)
In fact, the point of the algorithm is that there *is* guessing on the future; in most nottoodegenerate cases, one can detect that a branch will lead to nowhere and cut it.
Thus, and still assuming that I did not misunderstand anything, the following set (which contains only one element) will only be returned after around
2^n
operations:sage: n=20; IntegerLists(n, length=n,max_part=1).list()Certainly some "cuts" can be added to detect when a partial sequence cannot be extended.
At this point, the complexity of the following is not linear as it ought to be (one should be able to do the detection work faster by caching critical data), but it definitely is polynomial with a small degree (most likely quadratic), and very far from 2^{n: }
sage: n=20; IntegerLists(n, length=n,max_part=1).list() sage: n=1000 sage: %time IntegerListsLex(n, length=n,max_part=1).list() CPU times: user 852 ms, sys: 25.5 ms, total: 877 ms Wall time: 831 ms sage: n=2000 sage: %time x = IntegerListsLex(n, length=n,max_part=1).list() CPU times: user 3.15 s, sys: 24.2 ms, total: 3.17 s Wall time: 3.15 s
Cheers,
Nicolas
comment:64 in reply to: ↑ 62 Changed 5 years ago by
Replying to bgillespie:
Thanks for the thorough comments
Indeed! Thanks Nathann and Jeroen; I know how much time this takes.
Now, guys, if I may, Brian would deserve some words of appreciation from you for all the hard work he put into this.
Nicolas
comment:65 in reply to: ↑ 27 ; followup: ↓ 82 Changed 5 years ago by
Replying to ncohen:
Helloooooooooooo,
Here are some comments (mostly doc) about the current branch
 About
An integer list is a list l of nonnegative integers, its parts. The length of l is the number of its parts Note Two valid integer lists are considered equivalent if they only differ by trailing zeroes.Unless the length of a list is the number of its nonzero entries, it does not seem to be properly defined.
The length of a list is the number of its entries, including entries of size zero. i.e. [2, 0, 1, 0] is a list of length 4. It is equivalent to the list [2, 0, 1], but has a different length.
The constraints on the lists are as follows:
 in what follows you use a variablel
often (probably one of the lists): could you say so explicitly?
I've added a note to that effect.
 It seems that currently the method accepts input that does not satisfy the constraints that you list, i.e.:
sage: IntegerListsLex(min_n=4) Integer lists of sum between 4 and 0 satisfying certain constraints sage: list(IntegerListsLex(min_n=4)) []Should they really be considered as 'constraints', if the code accepts them and returns sensible output (i.e. empty sets)? When I read those lines, I expected the code to raise a
ValueError
exception on them.
The results from the algorithm should be mathematically correct if an error isn't raisedin this case, the set of such lists is empty, as advertised. While I was working through the initialization code yesterday, I did notice that it would be reasonable to include as few constraints on the initialization as possible and just give an empty output when conditions are contradictory, but I didn't have time to ensure that the algorithm was sound under arbitrary permutations of bad constraints. At the moment, everything that is returned should be correct.
Lower and upper bounds
: the text about constant values for floor/ceiling belongs to the INPUT block.
Updated.
waiver
 the description ofwaiver
in the INPUT block is very mysterious. If it is only meant for internal purposes, could you say so in its description?
Also updated. The waiver parameter is meant to be userfacing; it's purpose is to suppress a warning raised when the input parameters can't be checked computationally for cases that don't hang. This situation can occur when the user specifies an arbitrary function for the floor and ceiling parameters, so the purpose here is to verify that the user has thought carefully about what they are asking the algorithm to compute.
Next we obtain all lists of sum 4 and length 4 such that l[i] <= i:
 missing backticks at the end.
Fixed.
 Comparative timings: should they really appear in the function's documentation? To me the trac ticket is the right place for that.
Probably not, that was mainly for comparison during development. It's also old at this point, so I'll add current comparative timings to another comment.
 There are two 'TESTS' sections
That is true. Fixed.
self.warning = False # warning for dangerous (but possibly valid) usage
 could say what this flag does?
This is mostly an internal marker, and just keeps track of whether we are in a potentially
hanging use case (custom user function) that requires a warning to the user. I've
changed it to self._warning
to indicate that it's an internal marker, and made
the comment more verbose for the curious.
 the INPUT blocks says that
n
can be a list. Could you add there an explanation of what it means?
Added an explanation. (This just allows you to specify multiple allowable values for the list sum.)
 About the message
warn("""When the user specifies a method, then (s)he is responsible that the algorithm will not hang. Also note that the specified function should start at 0 rather than 1. Before trac#17979 the indexing was ambiguous and sometimes started at 1.""")From time to time we receive bug reports on sagedevel or sagesupport in which the users beg us to forgive them in case what they think might be a bug could actually be their mistake. Could this message be changed to something more
technical
? Something like `you defined ceiling=[...] to be a function, and we cannot swear that this call will not hang`?
Updated the message to be more specific about the issue.
 About the copyright header: I never saw any patch remove the name of other persons in a copyright header. Don't know what the policy is.
# Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>, # Copyright (C) 2012 Travis Scrimshaw <tscrim@ucdavis.edu> +# Copyright (C) 2015 Bryan Gillespie <Brg008@gmail.com>,
The update is a complete rewrite, so probably a new author list makes sense.
 Bryan
comment:66 Changed 5 years ago by
 Commit changed from 6153cf8d39dc23cb41a3d0c2ea66ba5dc3abd2c0 to cb18ced22db714063e744bb907a035b4fe3afa24
Branch pushed to git repo; I updated commit sha1. New commits:
cb18ced  17979 Updates primarily to documentation of combinat/integer_list.py in response to comment 27 in trac ticket 17979

comment:67 Changed 5 years ago by
Here are some comparative timings Re: the ones stripped from the docs.
sage: from sage.combinat.integer_list_old import IntegerListsLex as IntegerListsLexOld sage: P = IntegerListsLex(n=20, max_slope=0, min_part=1) sage: %time x = list(P) CPU times: user 159 ms, sys: 25.8 ms, total: 185 ms Wall time: 164 ms sage: P = IntegerListsLexOld(n=20, max_slope=0, min_part=1) sage: %time x = list(P) CPU times: user 170 ms, sys: 12.9 ms, total: 183 ms Wall time: 162 ms sage: len(x) 627 sage: P = IntegerListsLex(n=30, max_slope=0, min_part=1) sage: %time x = list(P) CPU times: user 1.74 s, sys: 21.9 ms, total: 1.76 s Wall time: 1.66 s sage: P = IntegerListsLexOld(n=30, max_slope=0, min_part=1) sage: %time x = list(P) CPU times: user 1.44 s, sys: 18.1 ms, total: 1.46 s Wall time: 1.42 s sage: len(x) 5604 sage: P = IntegerListsLex(n=40, max_slope=0, min_part=1) sage: %time x = list(P) CPU times: user 12.8 s, sys: 0 ns, total: 12.8 s Wall time: 12.7 s sage: P = IntegerListsLexOld(n=40, max_slope=0, min_part=1) sage: %time x = list(P) CPU times: user 10.3 s, sys: 1.98 ms, total: 10.3 s Wall time: 10.3 s sage: len(x) 37338 sage: P = IntegerListsLex(n=50, max_slope=0, min_part=1) sage: %time x = list(P) CPU times: user 1min 20s, sys: 216 ms, total: 1min 20s Wall time: 1min 20s sage: P = IntegerListsLexOld(n=50, max_slope=0, min_part=1) sage: %time x = list(P) CPU times: user 1min 1s, sys: 153 ms, total: 1min 2s Wall time: 1min 2s sage: len(x) 204226 sage: P = IntegerListsLex(n=60, max_slope=0, min_part=1) sage: %time x = list(P) CPU times: user 7min 5s, sys: 823 ms, total: 7min 6s Wall time: 7min 5s sage: P = IntegerListsLexOld(n=60, max_slope=0, min_part=1) sage: %time x = list(P) CPU times: user 5min 12s, sys: 495 ms, total: 5min 12s Wall time: 5min 12s sage: len(x) 966467
comment:68 in reply to: ↑ 34 ; followup: ↓ 72 Changed 5 years ago by
Replying to jdemeyer:
Why do you want to supporting
floor
andceiling
being a number? We already havemin_part
andmax_part
for that.
The main reason is that min_part
and max_part
are redundant in purpose with floor
and ceiling
, so the hope would be to deprecate that usage at some point. In the current implementation, all of the cases that can be handled with min_part
and max_part
plus floor
and ceiling
can also be handled using floor
and ceiling
alone.
comment:69 in reply to: ↑ 36 ; followup: ↓ 94 Changed 5 years ago by
Replying to jdemeyer:
Is this really true?
Before trac#17979 the indexing was ambiguous and sometimes started at 1.
There were places in the code of the old integer_list.py that used either convention, and integer_vector.py consistently started indexing at 1.
comment:70 in reply to: ↑ 39 ; followup: ↓ 74 Changed 5 years ago by
Replying to jdemeyer:
There is still this bug:
sage: it = iter(IntegerListsLex(4)) sage: for _ in range(20): print next(it) [4] [3, 1] [3, 0, 1] [3, 0, 0, 1] [3, 0, 0, 0, 1] [3, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]It seems that
[1,3]
will never appear in the output!
Not a bug, but an issue that's worth discussing. The premise of IntegerListsLex?, as I understand it, is that it should return integer lists satisfying certain constraints, in lexicographic ordering, starting with the largest. The lists returned in your example are exactly what they should be for this specificationnone of them is smaller than [1,3]
in lex ordering, since the 4
or 3
in the first position is larger than the corresponding 1
.
The issue is in specifying a priori a total ordering on the set that may not be isomorphic with that on NN (in fact, may not even be wellordered). Does it even make sense to call an object which iterates through a proper countable subset of a set an iterator? On the other hand, the iteration itself might still be useful in this case.
At the very least, this behavior is shared with that of the old implementation.
comment:71 in reply to: ↑ 48 Changed 5 years ago by
Replying to jdemeyer:
I dislike the fact that the warning shows even in cases where the output is obviously finite:
sage: IntegerListsLex(5, ceiling=lambda i:i, length=5) /usr/local/src/sageconfig/local/lib/python2.7/sitepackages/sage/combinat/integer_list.py:606: UserWarning: When the user specifies a method, then (s)he is responsible that the algorithm will not hang. Also note that the specified function should start at 0 rather than 1. Before trac#17979 the indexing was ambiguous and sometimes started at 1. Before trac#17979 the indexing was ambiguous and sometimes started at 1.""") Integer lists of sum 5 satisfying certain constraintsAlso note that the formatting of the warning is not quite right.
I updated the formatting of the warning (also the message to be more explicit/verbose), so check if it looks reasonable to you.
Here's what our thought process was concerning when to raise a warning message. We could easily do some additional computations to find certain cases where the specified parameters make giving a custom function safe. However, one of the complaints with the old version was that it was difficult to understand how the parameters affected the output. If we make it "sometimes" verifiably safe to use a custom function, depending on the circumstances, then that's another point of complexity for the user to followbut if we just raise a warning whenever a user uses a custom floor or ceiling function (but only if they haven't "signed a waiver" by specifying waiver=True
), that simplifies the interface for the user.
Also note that the example you gave could be handled by the following specification without raising a warning:
sage: IntegerListsLex(5, ceiling=[0,1,2,3,4], length=5)
comment:72 in reply to: ↑ 68 ; followup: ↓ 75 Changed 5 years ago by
Replying to bgillespie:
The main reason is that
min_part
andmax_part
are redundant in purpose withfloor
andceiling
, so the hope would be to deprecate that usage at some point.
I disagree. The advantage of min_part
and max_part
is they are known to be constant, which can lead to optimizations which cannot be done with floor
and ceiling
functions. Even if you don't do these optimizations at the moment, I would leave open the possibility of doing that in the future (I do so in #17920).
comment:73 in reply to: ↑ 56 Changed 5 years ago by
Replying to jdemeyer:
This limitation should be mentioned somewhere in the docs:
sage: IntegerListsLex(length=2, max_n=Infinity, ceiling=[Infinity, 0], floor=[0,1]).list() Traceback (most recent call last): ... ValueError: infinite upper bound for values of m(this is another example which "just works" with #17920).
I have plans to implement some parameter adjustments and cardinality checking for the cases when a user doesn't specify a custom floor or ceiling function which would catch this issue. Currently the code doesn't do any extra handling on cases where the floor and ceiling functions intersect, so currently it tries to find the largest possible value for the first position in the list, and determines that there is no largest one. The new checks would also make use of the slope conditions to catch something like:
sage: IntegerListsLex(length=3, max_n=Infinity, max_slope=1, ceiling=[Infinity, 1, 3], floor=[0, 1, 3])
For the moment, it does raise an error in this kind of situation, but it also doesn't hang or return an incorrect result. It also might be useful to give a more descriptive error message for when the possible values in a position are unbounded.
comment:74 in reply to: ↑ 70 ; followup: ↓ 76 Changed 5 years ago by
Replying to bgillespie:
Replying to jdemeyer:
It seems that
[1,3]
will never appear in the output!Not a bug, but an issue that's worth discussing.
It is a bug, see also the discussion starting at 29:ticket:17548.
comment:75 in reply to: ↑ 72 ; followup: ↓ 85 Changed 5 years ago by
Replying to jdemeyer:
Replying to bgillespie:
The main reason is that
min_part
andmax_part
are redundant in purpose withfloor
andceiling
, so the hope would be to deprecate that usage at some point.I disagree. The advantage of
min_part
andmax_part
is they are known to be constant, which can lead to optimizations which cannot be done withfloor
andceiling
functions. Even if you don't do these optimizations at the moment, I would leave open the possibility of doing that in the future (I do so in #17920).
Note that floor
and ceiling
take multiple different types of parameters, not just functions. This code checks for the type of the input parameter and optimizes when using a constant or a list of integers.
comment:76 in reply to: ↑ 74 ; followup: ↓ 83 Changed 5 years ago by
Replying to jdemeyer:
Replying to bgillespie:
Replying to jdemeyer:
It seems that
[1,3]
will never appear in the output!Not a bug, but an issue that's worth discussing.
It is a bug, see also the discussion starting at 29:ticket:17548.
Yes, I have glanced through that discussion.
The point is that if it is a bug, then it's a bug in the specification, not the code, since we are requiring the output to be in lexicographic order. However, if we don't want to call it an iterator because it doesn't satisfy the contract of eventually reaching every element in the set, then the class won't interact well with the many places that use iterators in Python and Sage. Can you propose a solution to this?
comment:77 in reply to: ↑ 59 ; followup: ↓ 84 Changed 5 years ago by
Replying to jdemeyer:
What's the point of setting
self.floor_type
if you don't use it?
I have plans to use it in an upcoming update which determines, in cases where a user doesn't specify custom functions, whether the set is finite/infinite, and if it can be enumerated in Lex ordering. (In particular this will be useful for properly setting the Category of the object, which currently defaults to FiniteEnumeratedSets
.
comment:78 Changed 5 years ago by
Hi Brian,
I should have some time tonight to work on this ticket. Let me know what your plans are to synchronize; in particular what areas I can hack in freely.
Thanks!
comment:79 Changed 5 years ago by
Hi Nicolas,
All my current changes are pushed to the ticketI made changes Re: comment 27, but haven't gotten to the other misc. changes suggested in various comments. I'll need to prepare a talk for a conference this weekend, so I'll only be able to put in parttime for the next few daysso feel free to hack wherever tonight. I'll check back in tomorrow during the day to look over some of the other recommendations from comments. Let me know if there's anything else you want me to look over then.
comment:80 Changed 5 years ago by
 Commit changed from cb18ced22db714063e744bb907a035b4fe3afa24 to 370068c5bab3821ce60ad216c732553de075f765
Branch pushed to git repo; I updated commit sha1. New commits:
370068c  17979: readded support for a list or iterable for n, using DistjointUnionEnumeratedSets; simplified code

comment:81 Changed 5 years ago by
 Commit changed from 370068c5bab3821ce60ad216c732553de075f765 to 3efcb0a067bb039d28d29b3fd8c9115c18c90d15
Branch pushed to git repo; I updated commit sha1. New commits:
3efcb0a  17979: Reworked documentation, and updated sage.combinat.tutorial

comment:82 in reply to: ↑ 65 Changed 5 years ago by
Hellooooo,
The length of a list is the number of its entries, including entries of size zero. i.e. [2, 0, 1, 0] is a list of length 4. It is equivalent to the list [2, 0, 1], but has a different length.
May I ask where in the function it is used that two lists are equivalent when they only differ by the number of trailing zeroes ?
If it is only when min_length<max_length
, could you add this mention as a note in the documentation of those parameters (input block)?
sage: IntegerListsLex(min_n=4) Integer lists of sum between 4 and 0 satisfying certain constraints sage: list(IntegerListsLex(min_n=4)) []Should they really be considered as 'constraints', if the code accepts them and returns sensible output (i.e. empty sets)? When I read those lines, I expected the code to raise a
ValueError
exception on them.The results from the algorithm should be mathematically correct if an error isn't raisedin this case, the set of such lists is empty, as advertised. While I was working through the initialization code yesterday, I did notice that it would be reasonable to include as few constraints on the initialization as possible and just give an empty output when conditions are contradictory, but I didn't have time to ensure that the algorithm was sound under arbitrary permutations of bad constraints.
Oh, the current behaviour is fine for me! If unsatisfiable parameters lead to an empty set there is no reason to complain: I was merely saying that the documentation made it sound like it was 'bad' to create such objects. Thus, I expected an exception. But if they are handled correctly, why is it even mentionned in the doc? Empty sets will be returned and so everything is fine, isn't it?
Also updated. The waiver parameter is meant to be userfacing; it's purpose is to suppress a warning raised when the input parameters can't be checked computationally for cases that don't hang. This situation can occur when the user specifies an arbitrary function for the floor and ceiling parameters, so the purpose here is to verify that the user has thought carefully about what they are asking the algorithm to compute.
I wonder about that... Instead of letting the code hang, wouldn't it be better to first "explore a bit the floor/ceiling parameters" ? If you see that up to 10^{10} all the values of ceiling do not sum to n, then say that something is wrong straight away?
This is mostly an internal marker, and just keeps track of whether we are in a potentially hanging use case (custom user function) that requires a warning to the user. I've changed it to
self._warning
to indicate that it's an internal marker, and made the comment more verbose for the curious.
Thanks,
Nathann
comment:83 in reply to: ↑ 76 ; followup: ↓ 103 Changed 5 years ago by
Replying to bgillespie:
The point is that if it is a bug, then it's a bug in the specification, not the code, since we are requiring the output to be in lexicographic order. However, if we don't want to call it an iterator because it doesn't satisfy the contract of eventually reaching every element in the set, then the class won't interact well with the many places that use iterators in Python and Sage. Can you propose a solution to this?
The are two possible solutions:
 raise an exception if the iterator doesn't iterate over all elements.
 drop the "lexicographic order" requirement.
comment:84 in reply to: ↑ 77 Changed 5 years ago by
Replying to bgillespie:
Replying to jdemeyer:
What's the point of setting
self.floor_type
if you don't use it?I have plans to use it in an upcoming update
In that case, I would prefer to introduce these attributes in that upcoming update.
comment:85 in reply to: ↑ 75 ; followup: ↓ 105 Changed 5 years ago by
Replying to bgillespie:
Note that
floor
andceiling
take multiple different types of parameters, not just functions. This code checks for the type of the input parameter and optimizes when using a constant or a list of integers.
However, without min_part
, there is absolutely no way to specify "floor
is a function which is always at least 1". I should be able to specify such an input with floor=myfunc, min_part=1
and the code can optimize this case better than when just specifying the function. 60 is an excellent example of this.
comment:86 followup: ↓ 90 Changed 5 years ago by
By the say, sorry for my earlier comment about the 2^n
runtime of the function. I am pretty sure I ran that test several times (reloading the branch in between) and that it was hanging with n=20
(running fine with n=10
, and slow with n=15
), but I cannot reproduce it now and the answer is immediate. Soooo well, my mistake O_o
Nathann
P.S.: currently, this branch keeps a copy of integer_list.py
as integer_list_old.py
.
comment:87 Changed 5 years ago by
 Commit changed from 3efcb0a067bb039d28d29b3fd8c9115c18c90d15 to 7b6838c3c12e1144949349bcef3697894d44f66d
comment:88 in reply to: ↑ 40 ; followup: ↓ 113 Changed 5 years ago by
Replying to jdemeyer:
This takes forever, even though the list trivially contains just one element:
sage: IntegerListsLex(10^100, max_length=1).list()
Thanks! This should be fixed now. I put in a test as well.
comment:89 in reply to: ↑ 46 ; followup: ↓ 91 Changed 5 years ago by
Replying to jdemeyer:
Remove
from sage.structure.list_clone import ClonableArray from sage.rings.integer import Integer
Why? ClonableArray? is used!
comment:90 in reply to: ↑ 86 ; followup: ↓ 99 Changed 5 years ago by
Replying to ncohen:
P.S.: currently, this branch keeps a copy of
integer_list.py
asinteger_list_old.py
.
This is because some other classes refer to next, first etc in combinat.integer_list which we do not have any longer in the new implementation. It is also useful right now to compare against the timing of the old implementation!
comment:91 in reply to: ↑ 89 Changed 5 years ago by
Replying to aschilling:
Why? ClonableArray? is used!
It was imported twice, but that's already fixed.
comment:92 Changed 5 years ago by
 Commit changed from 7b6838c3c12e1144949349bcef3697894d44f66d to ba68b9d7d80c4c50f124d803f21e3a07b92187d6
comment:93 Changed 5 years ago by
 Commit changed from ba68b9d7d80c4c50f124d803f21e3a07b92187d6 to e03611509b03f79e1c55b2cc347a427fc51a9f51
Branch pushed to git repo; I updated commit sha1. New commits:
e036115  17919: infinity > _infinity

comment:94 in reply to: ↑ 69 Changed 5 years ago by
Replying to bgillespie:
Replying to jdemeyer:
Is this really true?
Before trac#17979 the indexing was ambiguous and sometimes started at 1.There were places in the code of the old integer_list.py that used either convention, and integer_vector.py consistently started indexing at 1.
Sorry, my bad: actually the 1based indexing was only used internally in the old IntegerListLex?
. I removed that comment.
comment:95 in reply to: ↑ 51 ; followup: ↓ 110 Changed 5 years ago by
Replying to jdemeyer:
What is
IntegerVectors
and why is it not an alias ofIntegerListsLex
?
Essentially it's a short hand for IntegerListsLex
when the length is fixed. Kind of like Partitions is a short hand for IntegerListsLex
when min_part=1
and max_slope=0
. It also adds some more methods, and specialized counting. In any case, this ticket is not really touching this class except for its interface to IntegerListsLex
.
comment:96 Changed 5 years ago by
 Commit changed from e03611509b03f79e1c55b2cc347a427fc51a9f51 to 39d1993d70a837967109be12de261f4f504901cc
Branch pushed to git repo; I updated commit sha1. New commits:
39d1993  17919: slightly better phrasing

comment:97 in reply to: ↑ 45 Changed 5 years ago by
Replying to jdemeyer:
Replying to nthiery:
And we will reuse everything we can from your work!
The following takes forever, which is a problem that I solved in #17920, so I'm slightly disappointed this doesn't really work:
sage: IntegerListsLex(499499, length=1000, min_slope=1).list()
Agreed. I am pretty sure that the lookahead could be improved to handle this properly (Bryan: probably by doing some dichotomy in m_interval). I am going to throw this in the examples as a reminder for further work on this in later tickets.
comment:98 Changed 5 years ago by
 Description modified (diff)
 Work issues support n in an iterable deleted
comment:99 in reply to: ↑ 90 ; followup: ↓ 100 Changed 5 years ago by
This is because some other classes refer to next, first etc in combinat.integer_list which we do not have any longer in the new implementation. It is also useful right now to compare against the timing of the old implementation!
It is also code which returns wrong results. If you insist on keeping it around, could you add a stopgap in there?
Nathann
comment:100 in reply to: ↑ 99 Changed 5 years ago by
It is also code which returns wrong results. If you insist on keeping it around, could you add a stopgap in there?
My mistake, it is there.
Nathann
comment:101 in reply to: ↑ 53 ; followup: ↓ 111 Changed 5 years ago by
Replying to jdemeyer:
Please use
Infinity
instead ofinfinity
such that, if we ever useInfinity
fromsage.rings.infinity
, we don't need to changeinfinity
toInfinity
everywhere.
I just changed infinity
to _infinity
to mark that we are currently doing something special; it's a one line change at the begining of the file to switch to _infinity=Infinity
when the later will be optimized (looking forward to it). That being said, I don't mind changing _infinity
to Infinity
in the code if you think this won't bring confusion.
comment:102 in reply to: ↑ 15 Changed 5 years ago by
Replying to jdemeyer:
I would be 1 to using
float('inf')
just because it's faster. The Right Thing to do is to use Sage'sInfinity
and optimize that.
Agreed, that's the right thing to do in the mid term. But for now float('inf')
does the job, and it will be one line change anyway once Infinity
will be optimized. So let's not add a dependency on it.
comment:103 in reply to: ↑ 83 Changed 5 years ago by
Replying to jdemeyer:
Replying to bgillespie:
The point is that if it is a bug, then it's a bug in the specification, not the code, since we are requiring the output to be in lexicographic order. However, if we don't want to call it an iterator because it doesn't satisfy the contract of eventually reaching every element in the set, then the class won't interact well with the many places that use iterators in Python and Sage. Can you propose a solution to this?
The are two possible solutions:
 raise an exception if the iterator doesn't iterate over all elements.
 drop the "lexicographic order" requirement.
Having alternative implementations that take the second route to
handle those cases is indeed a worthwhile goal. But that's not
IntegerListsLex
's job :)
Here, we shall aim for 1., whenever possible: that is systematically when floor/ceiling are not functions, and when it's obvious and cheap otherwise.
Cheers,
Nicolas
comment:104 Changed 5 years ago by
Bryan: it would be useful if all the attributes self.floor
, ... were specified, typically in comments above or in the __init__
method.
Btw: shall we rename those attributes as self._floor
to mark them as private?
comment:105 in reply to: ↑ 85 ; followup: ↓ 112 Changed 5 years ago by
Replying to jdemeyer:
Replying to bgillespie:
Note that
floor
andceiling
take multiple different types of parameters, not just functions. This code checks for the type of the input parameter and optimizes when using a constant or a list of integers.However, without
min_part
, there is absolutely no way to specify "floor
is a function which is always at least 1". I should be able to specify such an input withfloor=myfunc, min_part=1
and the code can optimize this case better than when just specifying the function. 60 is an excellent example of this.
We were experimenting a bit with the API to try to minimize redundancy. At this point, I have settled for:
min_part
to specify a lower bound for all partsfloor
to specify lower bounds on the individual parts
What do you think?
Question: if the users passes floor=f, min_part=i
should IntegerListsLex
assume that f(k)
is always at most i
, or should it wrap f
to add this guarantee? At this point it does the latter, which of course adds a bit of overhead (which could be tamed with appropriate caching which we will anyway want to do during the Cythonization).
comment:106 in reply to: ↑ 56 ; followup: ↓ 114 Changed 5 years ago by
Replying to jdemeyer:
This limitation should be mentioned somewhere in the docs:
sage: IntegerListsLex(length=2, max_n=Infinity, ceiling=[Infinity, 0], floor=[0,1]).list() Traceback (most recent call last): ... ValueError: infinite upper bound for values of m(this is another example which "just works" with #17920).
I added this to the documentation, specifying that this example could be enumerated in lexicographically increasing order but not in lexicographically decreasing order as does IntegerListsLex
.
Two questions:
 Does anyone have a good suggestion for a better error message?
 Should the error message be created upon creating the parent, or when starting the iteration? The advantage of doing it only upon iteration is that we can still use the parent for checking containment, constructing the polytope, ...
comment:107 Changed 5 years ago by
 Commit changed from 39d1993d70a837967109be12de261f4f504901cc to f8f9a0202625c2eaaccfd8fb35f7ce95e495dc1a
Branch pushed to git repo; I updated commit sha1. New commits:
f8f9a02  17919: imported Jeroen's example from trac

comment:108 Changed 5 years ago by
I believe I have taken care of Jeroen's stylistic comments about raising execptions, type or not implemented errors instead of value errors, comment:47,
comment:109 followup: ↓ 130 Changed 5 years ago by
OSError: [combinat ] /usr/local/src/sageconfig/local/lib/python2.7/sitepackages/sage/combinat/integer_list.py:docstring of sage.combinat.integer_list.IntegerListsLex:370: WARNING: Literal block expected; none found.
comment:110 in reply to: ↑ 95 ; followup: ↓ 122 Changed 5 years ago by
Replying to nthiery:
In any case, this ticket is not really touching this class except for its interface to
IntegerListsLex
.
Looking at the diff, I see lots of changes to integer_vector.py
.
comment:111 in reply to: ↑ 101 Changed 5 years ago by
Replying to nthiery:
That being said, I don't mind changing
_infinity
toInfinity
in the code if you think this won't bring confusion.
I would prefer Infinity
.
comment:112 in reply to: ↑ 105 Changed 5 years ago by
Replying to nthiery:
At this point, I have settled for:
min_part
to specify a lower bound for all partsfloor
to specify lower bounds on the individual partsWhat do you think?
Question: if the users passes
floor=f, min_part=i
shouldIntegerListsLex
assume thatf(k)
is always at mosti
, or should it wrapf
to add this guarantee? At this point it does the latter.
The latter is the approach I took at #17920, so I agree completely :)
It fits well with the philosophy that all constraints have to be taken into account.
comment:113 in reply to: ↑ 88 Changed 5 years ago by
Replying to aschilling:
Replying to jdemeyer:
This takes forever, even though the list trivially contains just one element:
sage: IntegerListsLex(10^100, max_length=1).list()Thanks! This should be fixed now. I put in a test as well.
I see you "fixed" this by adding one small heuristic, but similar examples still don't work:
sage: IntegerListsLex(10^100, length=2, min_slope=2, max_slope=2).list() ...
comment:114 in reply to: ↑ 106 ; followup: ↓ 123 Changed 5 years ago by
Replying to nthiery:
 Should the error message be created upon creating the parent, or when starting the iteration? The advantage of doing it only upon iteration is that we can still use the parent for checking containment, constructing the polytope, ...
During iteration, mainly because I think that expensive checks should not be done during __init__
.
comment:115 Changed 5 years ago by
 Commit changed from f8f9a0202625c2eaaccfd8fb35f7ce95e495dc1a to 1a1fac1f7de8d5ae8d45138c594f7c8531024cbb
comment:116 Changed 5 years ago by
The tree traversal code in the iterator class needed some cleanup to make it more clear what was supposed to be happening where, so I did that in the above commit. I checked the running time to make sure it wasn't affected, and it seems to run as quickly as it did before the modifications.
comment:117 followups: ↓ 118 ↓ 128 Changed 5 years ago by
Hello !
I just finished reading the iterator part of that patch, and it looks solid.
Just a couple of details:
 Shouldn't
i in ZZ
appear before the others in the following line ?
return lambda i: l[i] if (i >= 0 and i < len(l) and i in ZZ) else default
 The documentation reads that
n
can be an iterable, but the code of__contains__
does not agree.
What features would be needed in this new version of integer_list
to get rid of the _old
one? We would be better without it.
Nathann
comment:118 in reply to: ↑ 117 ; followup: ↓ 121 Changed 5 years ago by
Replying to ncohen:
What features would be needed in this new version of
integer_list
to get rid of the_old
one? We would be better without it.
Let's first fix IntegerLists
(Lex
), we can remove integer_list_old.py
later.
comment:119 Changed 5 years ago by
 Commit changed from 1a1fac1f7de8d5ae8d45138c594f7c8531024cbb to c2705b80d619c99317b1a4ad780f28ea513361d1
Branch pushed to git repo; I updated commit sha1. New commits:
c2705b8  17979: ReST fix + updated doctest

comment:120 Changed 5 years ago by
 Commit changed from c2705b80d619c99317b1a4ad780f28ea513361d1 to 01ef7dbbc89b07b8dd583a0546e94497bf6aee18
Branch pushed to git repo; I updated commit sha1. New commits:
01ef7db  17979: _infinity > Infinity

comment:121 in reply to: ↑ 118 ; followup: ↓ 126 Changed 5 years ago by
Let's first fix
IntegerLists
(Lex
), we can removeinteger_list_old.py
later.
Yes probably. There is a stogap in there, and nobody knows that this file exists, so it is not too dangerous. I was just wondering what the new code couldn't do that the old one handled.
Nathann
comment:122 in reply to: ↑ 110 ; followup: ↓ 124 Changed 5 years ago by
Replying to jdemeyer:
Replying to nthiery:
In any case, this ticket is not really touching this class except for its interface to
IntegerListsLex
.Looking at the diff, I see lots of changes to
integer_vector.py
.
Oh, right, I forgot that I had used the occasion to get rid of quite some code in IntegerVectors
by using inheritance. Nevertheless, the main point remains: the API of IntegerVectors
hasn't changed; only its relation to IntegerListsLex
.
comment:123 in reply to: ↑ 114 Changed 5 years ago by
Replying to jdemeyer:
Replying to nthiery:
 Should the error message be created upon creating the parent, or when starting the iteration? The advantage of doing it only upon iteration is that we can still use the parent for checking containment, constructing the polytope, ...
During iteration, mainly because I think that expensive checks should not be done during
__init__
.
Sounds good.
comment:124 in reply to: ↑ 122 ; followup: ↓ 129 Changed 5 years ago by
Replying to nthiery:
Oh, right, I forgot that I had used the occasion to get rid of quite some code in
IntegerVectors
by using inheritance. Nevertheless, the main point remains: the API ofIntegerVectors
hasn't changed; only its relation toIntegerListsLex
.
Perhaps such changes would better be done in a different ticket, it can only increase the changes of this ticket getting merged.
comment:125 Changed 5 years ago by
 Commit changed from 01ef7dbbc89b07b8dd583a0546e94497bf6aee18 to 3530b5383cb02406034f6a1c8ffa2de50f777455
comment:126 in reply to: ↑ 121 Changed 5 years ago by
I was just wondering what the new code couldn't do that the old one handled.
Basicaclly just the next
and prev
features. There is a single spot using next
in the Sage library (in Compositions
IIRC), and I doubt they are much used elsewhere.
next
should be rather straightforward to implement if someone needs it. I created #18058 for this.
comment:127 Changed 5 years ago by
 Commit changed from 3530b5383cb02406034f6a1c8ffa2de50f777455 to 8e51e7ba310308d0ef8787519986d01ca24bc79e
comment:128 in reply to: ↑ 117 Changed 5 years ago by
Replying to ncohen:
I just finished reading the iterator part of that patch, and it looks solid.
Cool :) Thanks for checking!
Just a couple of details:
 Shouldn't
i in ZZ
appear before the others in the following line ?
return lambda i: l[i] if (i >= 0 and i < len(l) and i in ZZ) else default
Given that this is a critical section and an internal function, I just changed this to assume that i is a non negative integer, and only check on i < len(l). Does this sound ok?
 The documentation reads that
n
can be an iterable, but the code of__contains__
does not agree.
This is because IntegerListsLex(n, ...)
returns a DisjointEnumeratedSets
of IntegerListsLex
's if n
is an iterable. This way all the rest of the code can just ignore the existence of this feature.
The downside is that __contains__
is slower (it will run through the different IntegerListsLex
, and check __contains__
there). Especially if the iterable is infinite. But that's not an important feature, so that's ok I believe.
comment:129 in reply to: ↑ 124 ; followup: ↓ 137 Changed 5 years ago by
Replying to jdemeyer:
Perhaps such changes would better be done in a different ticket, it can only increase the changes of this ticket getting merged.
Yeah, I see your point. If really needed, we could do that. But this means some non trivial work. It was quicker to first cleanup the interface between IntegerVectors
and IntegerListsLex
before adapting it to the new IntegerListsLex
.
Ah, I should mention that there probably will be a minor conflict with #17927. I can handle the merge in #17927 once this one is finalized.
comment:130 in reply to: ↑ 109 Changed 5 years ago by
Replying to jdemeyer:
OSError: [combinat ] /usr/local/src/sageconfig/local/lib/python2.7/sitepackages/sage/combinat/integer_list.py:docstring of sage.combinat.integer_list.IntegerListsLex:370: WARNING: Literal block expected; none found.
Fixed.
comment:131 Changed 5 years ago by
 Description modified (diff)
comment:132 Changed 5 years ago by
 Commit changed from 8e51e7ba310308d0ef8787519986d01ca24bc79e to da793a3bf5508f3ef375aa6fded1c7b7a0a51acb
comment:133 in reply to: ↑ 39 Changed 5 years ago by
Replying to jdemeyer:
There is still this bug:
sage: it = iter(IntegerListsLex(4)) sage: for _ in range(20): print next(it) [4] [3, 1] [3, 0, 1] [3, 0, 0, 1] [3, 0, 0, 0, 1] [3, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]It seems that
[1,3]
will never appear in the output!
With the last commit this should be fixed!
comment:134 Changed 5 years ago by
 Commit changed from da793a3bf5508f3ef375aa6fded1c7b7a0a51acb to fcaa99cd2b40c3e85a7d15b4775983eb300ead24
Branch pushed to git repo; I updated commit sha1. New commits:
fcaa99c  17979: added comment to _check_lexicographic_iterable, and inserted example by Jeroen

comment:135 Changed 5 years ago by
Hello !
I still get an error upon "make docclean && make dochtml"
OSError: [combinat ] /home/ncohen/.Sage/local/lib/python2.7/sitepackages/sage/combinat/integer_list.py:docstring of sage.combinat.integer_list.IntegerListsLex:338: WARNING: undefined label: _sectiongenericintegerlistlex (if the link has no caption the label must precede a section header)
Nathann
comment:136 followups: ↓ 145 ↓ 161 Changed 5 years ago by
Replace
raise ValueError("The specified parameters do not allow for a lexicographic iterator!")
by
raise RuntimeError("the specified parameters do not allow for a lexicographic iterator")
comment:137 in reply to: ↑ 129 ; followups: ↓ 142 ↓ 164 Changed 5 years ago by
Replying to nthiery:
Replying to jdemeyer:
Perhaps such changes would better be done in a different ticket, it can only increase the changes of this ticket getting merged.
Yeah, I see your point. If really needed, we could do that. But this means some non trivial work.
It think it is quite trivial to split it up, just make IntegerVectors
use integer_list_old.py
. You will also avoid the conflict with #17927 this way.
comment:138 Changed 5 years ago by
This hangs (please add this as doctest when you fix it):
sage: L = IntegerListsLex(ceiling=[0], min_slope=1, max_slope=1) sage: it = iter(L) sage: for _ in range(10): ....: print next(it)
comment:139 Changed 5 years ago by
This should be added as a different example which cannot be iterated in lexicographic order:
sage: L = IntegerListsLex(ceiling=[0], min_slope=1, max_slope=2)
comment:140 followup: ↓ 148 Changed 5 years ago by
Please add also this example:
sage: sage: L = IntegerListsLex(ceiling=[1], min_slope=1, max_slope=1) sage: it = iter(L) sage: for _ in range(10): ....: print next(it)
comment:141 followups: ↓ 152 ↓ 175 Changed 5 years ago by
Concerning terminology: is "lexicographic order" really the standard way of refering to this ordering? I would call it "reverse lexicographic" because it starts with the largest element first (but I'm not in combinatorics, so if this is standard, then it's fine).
However, I do think this "lexicographic order" needs to be documented somewhere, especially with the behaviour of implicit trailing zeros. Add this example, because it might look counterintuitive that the [1]
appears in the middle here:
sage: list(IntegerListsLex(max_length=4, max_part=1)) [[1, 1, 1, 1], [1, 1, 1], [1, 1, 0, 1], [1, 1], [1, 0, 1, 1], [1, 0, 1], [1, 0, 0, 1], [1], [0, 1, 1, 1], [0, 1, 1], [0, 1, 0, 1], [0, 1], [0, 0, 1, 1], [0, 0, 1], [0, 0, 0, 1], []]
comment:142 in reply to: ↑ 137 ; followup: ↓ 143 Changed 5 years ago by
Replying to jdemeyer:
Replying to nthiery:
Replying to jdemeyer:
Perhaps such changes would better be done in a different ticket, it can only increase the changes of this ticket getting merged.
Yeah, I see your point. If really needed, we could do that. But this means some non trivial work.
It think it is quite trivial to split it up, just make
IntegerVectors
useinteger_list_old.py
. You will also avoid the conflict with #17927 this way.
Note that IntegerVectors
is used in other classes, such as Partitions
, so if we wanted to leave it referencing integer_list_old.py
, then we would probably also want to port the uses of IntegerVectors
to IntegerListsLex
wherever that occurs in the library. IntegerVectors
also uses some auxiliary input formats such as inner=[...]
and outer=[...]
, so we would need to support those in IntegerListsLex
if we wanted to use this approach. Feels a little like a separate ticket to me, but it certainly could be done.
comment:143 in reply to: ↑ 142 Changed 5 years ago by
Replying to bgillespie:
Note that
IntegerVectors
is used in other classes, such asPartitions
, so if we wanted to leave it referencinginteger_list_old.py
, then we would probably also want to port the uses ofIntegerVectors
toIntegerListsLex
wherever that occurs in the library.IntegerVectors
also uses some auxiliary input formats such asinner=[...]
andouter=[...]
, so we would need to support those inIntegerListsLex
if we wanted to use this approach. Feels a little like a separate ticket to me, but it certainly could be done.
I don't quite understand your comment, but my proposal is: on this ticket, fix only IntegerListsLex
and leave the rest for followup tickets.
comment:144 Changed 5 years ago by
 Commit changed from fcaa99cd2b40c3e85a7d15b4775983eb300ead24 to ba6db5768d13c38b5a3cf90de75aa847c6c51efe
Branch pushed to git repo; I updated commit sha1. New commits:
ba6db57  17979 changed ValueError to RuntimeError and lex order to reverse lex order

comment:145 in reply to: ↑ 136 Changed 5 years ago by
Replying to jdemeyer:
Replace
raise ValueError("The specified parameters do not allow for a lexicographic iterator!")by
raise RuntimeError("the specified parameters do not allow for a lexicographic iterator")
Fixed. Also changed lex order to reverse lex order!
comment:146 Changed 5 years ago by
 Commit changed from ba6db5768d13c38b5a3cf90de75aa847c6c51efe to 0a80fd49fed43754d61af0a02633394877f7ba63
Branch pushed to git repo; I updated commit sha1. New commits:
0a80fd4  17979: fixed crosslink

comment:147 Changed 5 years ago by
 Commit changed from 0a80fd49fed43754d61af0a02633394877f7ba63 to 56e831a1e2bbde6ccac2b883e69987b743201a37
comment:148 in reply to: ↑ 140 Changed 5 years ago by
Replying to jdemeyer:
Please add also this example:
sage: sage: L = IntegerListsLex(ceiling=[1], min_slope=1, max_slope=1) sage: it = iter(L) sage: for _ in range(10): ....: print next(it)
Fixed. The _check_lexicographic_iterable now also catches that this is not enumeratable under reverse lex order. I added the two tests that you mentioned.
comment:149 Changed 5 years ago by
 Commit changed from 56e831a1e2bbde6ccac2b883e69987b743201a37 to 709f9ccfa7fe584febf107fe84e5e5303a5b292d
Branch pushed to git repo; I updated commit sha1. New commits:
709f9cc  17979 added Jeroen's example about trailing zeroes

comment:150 followup: ↓ 153 Changed 5 years ago by
What do you think of that ?
sage: [2,2,0] in IntegerListsLex(4,min_length=3,max_length=4) # appears in .list() True sage: [2,2,0,0] in IntegerListsLex(4,min_length=3,max_length=4) # does not appear in .list() True sage: [2,2,0,0,0] in IntegerListsLex(4,min_length=3,max_length=4) # does not appear in .list() False
Nathann
comment:151 Changed 5 years ago by
 Commit changed from 709f9ccfa7fe584febf107fe84e5e5303a5b292d to 652a6d552c10b95fd3c735094fe105e4081e47ce
Branch pushed to git repo; I updated commit sha1. New commits:
652a6d5  17979 fixed doc compilation issue

comment:152 in reply to: ↑ 141 Changed 5 years ago by
Replying to jdemeyer:
Concerning terminology: is "lexicographic order" really the standard way of refering to this ordering? I would call it "reverse lexicographic" because it starts with the largest element first (but I'm not in combinatorics, so if this is standard, then it's fine).
However, I do think this "lexicographic order" needs to be documented somewhere, especially with the behaviour of implicit trailing zeros. Add this example, because it might look counterintuitive that the
[1]
appears in the middle here:sage: list(IntegerListsLex(max_length=4, max_part=1)) [[1, 1, 1, 1], [1, 1, 1], [1, 1, 0, 1], [1, 1], [1, 0, 1, 1], [1, 0, 1], [1, 0, 0, 1], [1], [0, 1, 1, 1], [0, 1, 1], [0, 1, 0, 1], [0, 1], [0, 0, 1, 1], [0, 0, 1], [0, 0, 0, 1], []]
Added. The doc compilation issues should also be fixed now!
comment:153 in reply to: ↑ 150 ; followups: ↓ 155 ↓ 156 Changed 5 years ago by
Replying to ncohen:
What do you think of that ?
sage: [2,2,0] in IntegerListsLex(4,min_length=3,max_length=4) # appears in .list() True sage: [2,2,0,0] in IntegerListsLex(4,min_length=3,max_length=4) # does not appear in .list() True sage: [2,2,0,0,0] in IntegerListsLex(4,min_length=3,max_length=4) # does not appear in .list() False
The reason for this behavior is the following: we identify elements which differ by trailing zeroes up to max_length. That is why the first and second example gives True and the last one gives False (since in this case we are beyond the max_length).
comment:154 in reply to: ↑ 45 Changed 5 years ago by
Replying to jdemeyer:
Replying to nthiery:
And we will reuse everything we can from your work!
The following takes forever, which is a problem that I solved in #17920, so I'm slightly disappointed this doesn't really work:
sage: IntegerListsLex(499499, length=1000, min_slope=1).list()
This example and
sage: IntegerListsLex(10^100, max_length=1).list()
will be optimized in #18055.
comment:155 in reply to: ↑ 153 ; followups: ↓ 157 ↓ 159 ↓ 165 Changed 5 years ago by
The reason for this behavior is the following: we identify elements which differ by trailing zeroes up to max_length. That is why the first and second example gives True and the last one gives False (since in this case we are beyond the max_length).
Soooooooooo when you get the list [2,2,0]
in the output of .list()
, it represents "all lists beginning by 2,2,0
whose length is included between 3 and 4"? This information is not included in the object itself, it is to be understood by how it was first produced.
This identification of list worries me a bit. The exception in __iter__
was added because we consider it a bug that some element of the set may never be listed in __iter__
, and this is exactly the problem we have again here. For a different reason, i.e. because some lists are identified.
Nathann
comment:156 in reply to: ↑ 153 Changed 5 years ago by
Replying to aschilling:
The reason for this behavior is the following: we identify elements which differ by trailing zeroes up to max_length.
The "up to max_length
" part is a bit arbitrary. I would prefer that these should give the same answer (either both True
or both False
):
sage: [2,2,0,0] in IntegerListsLex(4,min_length=3,max_length=4) sage: [2,2,0,0,0] in IntegerListsLex(4,min_length=3,max_length=4)
comment:157 in reply to: ↑ 155 Changed 5 years ago by
Replying to ncohen:
This identification of list worries me a bit. The exception in
__iter__
was added because we consider it a bug that some element of the set may never be listed in__iter__
, and this is exactly the problem we have again here. For a different reason, i.e. because some lists are identified.
It's pretty natural to follow this equivalence (think for instance monomials x*y^2
and x*y^2*z^0
), but I definitely see your point. Would it be useful to specify a more featureful class IntegerList
(returned by this class) which takes into account these equivalences and provides comparison operations for lexicographic ordering? This would help to make more clear the assumptions being made on the lists during iteration, and would result in both IntegerList([2,2,0,0])
and IntegerList([2,2,0,0,0])
being contained in IntegerListsLex(4,min_length=3,max_length=4)
in the example above, since they are the same object, and at least one representative satisfies the desired criterion.
comment:158 Changed 5 years ago by
 Commit changed from 652a6d552c10b95fd3c735094fe105e4081e47ce to ae225b3af4329dcbedbbfe83151a000b09ef44d3
Branch pushed to git repo; I updated commit sha1. New commits:
ae225b3  17979: reverse lexicographic > inverse lexicographic

comment:159 in reply to: ↑ 155 Changed 5 years ago by
Replying to ncohen:
The reason for this behavior is the following: we identify elements which differ by trailing zeroes up to max_length. That is why the first and second example gives True and the last one gives False (since in this case we are beyond the max_length).
Soooooooooo when you get the list
[2,2,0]
in the output of.list()
, it represents "all lists beginning by2,2,0
whose length is included between 3 and 4"? This information is not included in the object itself, it is to be understood by how it was first produced.
The parent knows about the min_length and max_length, so it makes sense to identify objects with trailing zeroes in the correct parameter range. In any case, this is the same behavior as in the old version of the code and I do not think we should change this here.
This identification of list worries me a bit. The exception in
__iter__
was added because we consider it a bug that some element of the set may never be listed in__iter__
, and this is exactly the problem we have again here. For a different reason, i.e. because some lists are identified.
Nathann, this is a different issue! The above issue is just about identifying objects, not about not listing all of them. The issue about not listing all of them is due to the fact that inverse lexicographic order intrinsically (by definition) does not list them all.
Anne
New commits:
ae225b3  17979: reverse lexicographic > inverse lexicographic

comment:160 Changed 5 years ago by
 Commit changed from ae225b3af4329dcbedbbfe83151a000b09ef44d3 to 0c5305c958517701a68b4419f8a173f544cbefd4
comment:161 in reply to: ↑ 136 ; followup: ↓ 169 Changed 5 years ago by
Replying to jdemeyer:
Replace
raise ValueError("The specified parameters do not allow for a lexicographic iterator!")by
raise RuntimeError("the specified parameters do not allow for a lexicographic iterator")
Really? RuntimeError
is "for an error that doesn’t fall in any of the
other categories", where as we do fit within the ValueError
category:
"when a builtin operation or function receives an argument that has
the right type but an inappropriate value". Here IntegerListsLex
did
receive inappropriate value which makes the lexicographic enumeration
improper.
Nicolas
comment:162 Changed 5 years ago by
 Commit changed from 0c5305c958517701a68b4419f8a173f544cbefd4 to 611f5c73f0d5b8af4c150abc1785e5ea305b164d
comment:163 in reply to: ↑ 33 ; followup: ↓ 170 Changed 5 years ago by
Replying to jdemeyer:
The heading should be formatted like http://www.sagemath.org/doc/developer/coding_basics.html#headingsofsagelibrarycodefiles (in particular, it's bad to mention the GPL without version number).
Yup: I made GPL into GPLv2+ and added a short history. However I kept the short version of the header without the four lines of verbiage. It's really inconvenient to have a bunch of useless information at the top of a file when this is the very first thing that pops up when opening a file. As far as I can remember, this was already discussed on sagedevel and considered ok.
In fact, I would vote for updating accordingly the dev manual, but that's another discussion.
New commits:
67450ee  17979: updated header

6819cf5  Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into ticket/17979

611f5c7  17979: GPL > GPL v2+

comment:164 in reply to: ↑ 137 ; followup: ↓ 182 Changed 5 years ago by
Replying to jdemeyer:
It think it is quite trivial to split it up, just make
IntegerVectors
useinteger_list_old.py
.
Thanks for the suggestion, but no :) I haven't spent so much time on
this to still have some non trivial usage of integer_list_old.py
lying around. If I don't find someone to review this very soon, I'll
reconsider.
comment:165 in reply to: ↑ 155 ; followup: ↓ 166 Changed 5 years ago by
Replying to ncohen:
Soooooooooo when you get the list
[2,2,0]
in the output of.list()
, it represents "all lists beginning by2,2,0
whose length is included between 3 and 4"? This information is not included in the object itself, it is to be understood by how it was first produced.This identification of list worries me a bit.
I agree: 15 years ago, from the use cases I had under hand, I though that this was a neat feature to identify lists up to trailing zeroes. However this is non trivial to specify properly, and I am now convinced that this is just a can of worms. We should seriously consider dropping this feature.
However I believe that this is out of the scope of this ticket, especially since this would require a change in the specifications, and cause backward incompatibilities. Up to the fuzziness in this piece of the specification, it sounds like the code should by now be correct w.r.t. the current specifications; let's get it done.
Cheers,
Nicolas
comment:166 in reply to: ↑ 165 Changed 5 years ago by
Replying to nthiery:
However I believe that this is out of the scope of this ticket, especially since this would require a change in the specifications
Where was it specified that lists with trailing zeros are identified up to max_length? It makes absolutely no sense at all that these two questions give a different answer:
sage: [2,2,0,0] in IntegerListsLex(4,min_length=3,max_length=4) sage: [2,2,0,0,0] in IntegerListsLex(4,min_length=3,max_length=4)
comment:167 Changed 5 years ago by
 Commit changed from 611f5c73f0d5b8af4c150abc1785e5ea305b164d to 46d01a95002b3b498c9af1ed6784fa0fd4960ae5
Branch pushed to git repo; I updated commit sha1. New commits:
46d01a9  17979: added Nathann's example of dubious behavior with trailing zeroes

comment:168 Changed 5 years ago by
For the record: I added a warning and Nathann's example in the doc about this.
New commits:
46d01a9  17979: added Nathann's example of dubious behavior with trailing zeroes

comment:169 in reply to: ↑ 161 ; followup: ↓ 172 Changed 5 years ago by
Replying to nthiery:
Replying to jdemeyer:
Replace
raise ValueError("The specified parameters do not allow for a lexicographic iterator!")by
raise RuntimeError("the specified parameters do not allow for a lexicographic iterator")Really?
RuntimeError
is "for an error that doesn’t fall in any of the other categories", where as we do fit within theValueError
category: "when a builtin operation or function receives an argument that has the right type but an inappropriate value". HereIntegerListsLex
did receive inappropriate value which makes the lexicographic enumeration improper.
Fine, I don't care so much (but there is also the formatting issue of not using a capital letter and exclamation mark). I felt that RuntimeError
was more appropriate because it is not really a specific value which is bad, but some computation based on the input values from which it can be concluded that the input is bad.
comment:170 in reply to: ↑ 163 ; followup: ↓ 174 Changed 5 years ago by
Replying to nthiery:
However I kept the short version of the header without the four lines of verbiage. It's really inconvenient to have a bunch of useless information at the top of a file when this is the very first thing that pops up when opening a file.
If you feel like this, then first change http://www.sagemath.org/doc/developer/coding_basics.html#headingsofsagelibrarycodefiles. Don't just change conventions on your own because you find it more convenient.
As far as I can remember, this was already discussed on sagedevel and considered ok.
I'd like to see a link to that discussion.
comment:171 Changed 5 years ago by
 Commit changed from 46d01a95002b3b498c9af1ed6784fa0fd4960ae5 to f634ab0b514edc2c62da1310420756163f616946
Branch pushed to git repo; I updated commit sha1. New commits:
f634ab0  17979: RuntimeError > ValueError + fixed message

comment:172 in reply to: ↑ 169 Changed 5 years ago by
Replying to jdemeyer:
Fine, I don't care so much (but there is also the formatting issue of not using a capital letter and exclamation mark).
formatting fixed.
I felt that
RuntimeError
was more appropriate because it is not really a specific value which is bad, but some computation based on the input values from which it can be concluded that the input is bad.
I agree that it's borderline.
New commits:
f634ab0  17979: RuntimeError > ValueError + fixed message

comment:173 Changed 5 years ago by
 Commit changed from f634ab0b514edc2c62da1310420756163f616946 to ad238f9f80726ac8b872a6bb44f6bfeeb243270b
Branch pushed to git repo; I updated commit sha1. New commits:
ad238f9  17979: formally compliant long copyright header

comment:174 in reply to: ↑ 170 Changed 5 years ago by
Replying to jdemeyer:
Replying to nthiery:
However I kept the short version of the header without the four lines of verbiage. It's really inconvenient to have a bunch of useless information at the top of a file when this is the very first thing that pops up when opening a file.
If you feel like this, then first change http://www.sagemath.org/doc/developer/coding_basics.html#headingsofsagelibrarycodefiles. Don't just change conventions on your own because you find it more convenient.
Will do.
For now I don't want to waste time on this stupid issue, so voilà, formal header there is.
New commits:
ad238f9  17979: formally compliant long copyright header

comment:175 in reply to: ↑ 141 Changed 5 years ago by
Replying to jdemeyer:
Concerning terminology: is "lexicographic order" really the standard way of refering to this ordering? I would call it "reverse lexicographic" because it starts with the largest element first (but I'm not in combinatorics, so if this is standard, then it's fine).
Yup, we indeed wanted to be more specific about this. This is done now. Note that we have used "inverse lexicographic" since "reverse lexicographic" usually means reading the words in reverse order.
http://en.wikipedia.org/wiki/Lexicographical_order#Reverse_lexicographic_order
comment:176 in reply to: ↑ 41 ; followup: ↓ 198 Changed 5 years ago by
Replying to jdemeyer:
Some implementations might not use keyword arguments for
length
, so themin_n
andmax_n
arguments (preferably renamed tomin_sum
andmax_sum
) should be moved towards the end of the argument list.
I'd be rather surprised if this was used anywhere (it was not in the Sage sources), especially since the documentation never mentionned this possibility. And it's neat to have all arguments be grouped by theme. But ok, better be safe than sorry. Done.
comment:177 Changed 5 years ago by
 Commit changed from ad238f9f80726ac8b872a6bb44f6bfeeb243270b to f73c43fd4423675f9ce279da9bb929a44db31483
comment:178 followup: ↓ 181 Changed 5 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
Ok, I believe all the points that have been raised have been catered for (but some may have slipped through in this long thread). So this is up for formal review.
Thanks for all the comments and suggestions!
Note: please see the description where I left two points where feedback is specifically welcome.
New commits:
9bf94c4  17979: moved min_sum and max_sum later in the __init__ arguments

f73c43f  17979: trivial doctest fix

comment:179 Changed 5 years ago by
 Reviewers set to Nathann Cohen, Jeroen Demeyer
comment:180 followup: ↓ 208 Changed 5 years ago by
I agree with this comment:
.. TODO:: Maybe this should be ``check=False`` instead?
The standard terminology for such an option is indeed check=False
and waiver
appears only in integer_list.py
.
comment:181 in reply to: ↑ 178 Changed 5 years ago by
Replying to nthiery:
Ok, I believe all the points that have been raised have been catered for (but some may have slipped through in this long thread). So this is up for formal review.
Let me remind everybody here that #17920 is also up for formal review.
Comparing both approaches (I am of course not completely unbiased, but I'll really try to be objective):
 Bugs: neither #17979 nor #17920 have obvious bugs (although I find 166 dubious at least), both fix #17548. I assume both pass doctests.
 Features: #17979 tries to replicate the old behaviour as closely as possible, #17920 generalizes certain conditions (e.g. allowing negative numbers; allowing iteration in noninvlex order) but also adds a few restrictions (e.g. not allowing an iterable for
n
).
 Interface with rest of Sage: #17920 only uses the new
IntegerLists
code forIntegerListsLex
,Partitions
andCompositions
(in the other places in Sage whereIntegerListsLex
was used, I didn't find any bugs so I left those). This ticket #17979 replaces the old code in almost all cases (except partially inIntegerVectors
).
comment:182 in reply to: ↑ 164 ; followup: ↓ 193 Changed 5 years ago by
Replying to nthiery:
Thanks for the suggestion, but no :) I haven't spent so much time on this to still have some non trivial usage of
integer_list_old.py
lying around. If I don't find someone to review this very soon, I'll reconsider.
For the record: I will not review the changes to integer_vector.py
on this ticket. If somebody else wants to do that, that's fine for me.
comment:183 Changed 5 years ago by
This is certainly false:
The complexity of the algorithm has not been formally proven, but the average runtime for producing each list `l` is suspected to be bounded by a lowdegree polynomial in ``lmax``, where ``lmax`` is the length of the longest list. Similarly, the space complexity of the algorithm is bounded by a lowdegree polynomial in ``lmax``.
(in fact, this statement is probably more true of #17920 than it is for #17979)
comment:184 followup: ↓ 188 Changed 5 years ago by
The code in _IntegerListsLexIter
needs to be documented much more, it is hard to understand the code without documentation. Since most of the internal state is contained in attributes like self.rho
, you should document what these mean (and # list of current search ranges
is not sufficient documentation).
Also: please use terminology consistently. I think the same thing is called "part", "entry" and "value" in different places.
comment:185 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:186 Changed 5 years ago by
 Description modified (diff)
comment:187 followup: ↓ 199 Changed 5 years ago by
This should return the list containg 1 element []
:
sage: list(IntegerListsLex(ceiling=[0], max_slope=0))
comment:188 in reply to: ↑ 184 ; followup: ↓ 206 Changed 5 years ago by
Since most of the internal state is contained in attributes like
self.rho
, you should document what these mean (and# list of current search ranges
is not sufficient documentation).
+1 to that. This terminology made it much harder for me to understand what the code was doing. Instead of writing this in the code:
self.rho = [] # list of current search ranges self.mu = [] # list of integers self.j = 1 # index of last element of mu self.nu = 0 # sum of values in mu
It would probably be clearer to rename those variables (respectively) as
self._search_range self._current_list self._j self._current_sum
Nathann
P.S.: And indeed, as Jeroen says, it would be cool to be a bit more verbose about what these things do. Once you know how the code works I agree that 'current search range' is a rather good explanation, but until you do it is rather crytic. I have firsthand knowledge of that ^^;
comment:189 followups: ↓ 192 ↓ 194 Changed 5 years ago by
I don't like this:
.. WARNING:: The specifications of this feature are fuzzy, leading to potentially surprising consequences (see the examples below). It is recommended not to rely on it, as it may eventually be discontinued.
The specifications are not fuzzy. They might be strange, unlogical, arbitrary, badly chosen but not fuzzy. To make it less fuzzy, you should document explicitly the fact that the equivalence only works up to max_length
in the NOTE
about this WARNING
.
(to compare: in #17920 I took the convention that x in L
is equivalent to x in L.list()
, so I don't really identify lists with trailing zeros, I just output the list with the least number of trailing zeros)
comment:190 followup: ↓ 209 Changed 5 years ago by
I would also prefer to remove the text concerning algorithmic complexity in src/sage/combinat/tutorial.py
. What I dislike most is that it seems to hide behind the "degenerate cases" exception without really specifying what that means.
comment:191 followups: ↓ 216 ↓ 218 Changed 5 years ago by
This hangs:
sage: list(IntegerListsLex(1, min_length=2, min_slope=0, max_slope=0))
(it works fine without the min_length
though)
comment:192 in reply to: ↑ 189 Changed 5 years ago by
I don't like this:
.. WARNING:: The specifications of this feature are fuzzy, leading to potentially surprising consequences (see the examples below). It is recommended not to rely on it, as it may eventually be discontinued.
+1 to that. I also fear that this warning may be used later as an authorization to not document behaviors and to overlook inconsistencies because it is, after all, 'documented'.
Nathann
comment:193 in reply to: ↑ 182 Changed 5 years ago by
Replying to jdemeyer:
For the record: I will not review the changes to
integer_vector.py
on this ticket.
Sure thing! That's what I had in mind.
comment:194 in reply to: ↑ 189 ; followups: ↓ 195 ↓ 197 Changed 5 years ago by
Replying to jdemeyer:
I don't like this:
.. WARNING:: The specifications of this feature are fuzzy, leading to potentially surprising consequences (see the examples below). It is recommended not to rely on it, as it may eventually be discontinued.The specifications are not fuzzy. They might be strange, unlogical, arbitrary, badly chosen but not fuzzy. To make it less fuzzy, you should document explicitly the fact that the equivalence only works up to
max_length
in theNOTE
about thisWARNING
.
Well, my point was: the specifications *as they are currently written* are fuzzy. I meant to propose an alternative specification, but somehow my comment did not make its way into trac. Here it is:
When several lists satisfying the constraint differ only by trailing zeroes, only the shortest one is enumerated (and therefore counted).
I believe this is not fuzzy anymore, and matches the current behavior of the code; and therefore does not require breaking backward compatibility at this stage.
What do you think?
As a separate question: do you believe like me that we should, in a later ticket, get rid of this "feature"?
Cheers,
Nicolas
comment:195 in reply to: ↑ 194 ; followup: ↓ 204 Changed 5 years ago by
Replying to nthiery:
When several lists satisfying the constraint differ only by trailing zeroes, only the shortest one is enumerated (and therefore counted).
constraint
> constraints
comment:196 followup: ↓ 203 Changed 5 years ago by
Please add this somewhere in __init__
:
if min_length < 0: min_length = 0
comment:197 in reply to: ↑ 194 ; followup: ↓ 207 Changed 5 years ago by
Replying to nthiery:
As a separate question: do you believe like me that we should, in a later ticket, get rid of this "feature"?
I do think that, by default, we shouldn't output lists with trailing zeros, since this will lead in many cases to infinitely many lists satisfying the constraints. However, I think it's best if the behaviour of __contains__
really matches the iterator.
If you ever allow negative parts, then the convention of having no trailing zeros becomes very strange, since "nonzero" is no longer a convex condition.
In #17920 I solved this by setting a minimum/maximum value for the last part of a list, if the list is longer than min_length
. By default, this minimum is 1 with no maximum which gives the same lists as the "identify trailing zeros" convention.
comment:198 in reply to: ↑ 176 ; followup: ↓ 202 Changed 5 years ago by
Replying to nthiery:
I'd be rather surprised if this was used anywhere (it was not in the Sage sources), especially since the documentation never mentionned this possibility.
Somebody had to change src/sage/combinat/integer_matrices.py
for this reason :)
comment:199 in reply to: ↑ 187 Changed 5 years ago by
Replying to jdemeyer:
This should return the list containg 1 element
[]
:sage: list(IntegerListsLex(ceiling=[0], max_slope=0))
This is fixed now!
comment:200 Changed 5 years ago by
 Commit changed from f73c43fd4423675f9ce279da9bb929a44db31483 to 31013b932d8f0c0e941713dc8e44c02cc323f5c5
Branch pushed to git repo; I updated commit sha1. New commits:
31013b9  17979: more checks on length, min_length, max_length

comment:201 Changed 5 years ago by
 Commit changed from 31013b932d8f0c0e941713dc8e44c02cc323f5c5 to 39ee52d817c0b10ad5795cc2b138a4a83475fc25
Branch pushed to git repo; I updated commit sha1. New commits:
39ee52d  17979: proper specification of the trailing zeroes 'feature'

comment:202 in reply to: ↑ 198 Changed 5 years ago by
Replying to jdemeyer:
Somebody had to change
src/sage/combinat/integer_matrices.py
for this reason :)
Good point :) Well, it was good to make this change anyway for clarity :)
comment:203 in reply to: ↑ 196 ; followup: ↓ 211 Changed 5 years ago by
Replying to jdemeyer:
Please add this somewhere in
__init__
:if min_length < 0: min_length = 0
I am not sure whether I prefer this, or barking, but that's fine. Done, together with further typechecks.
comment:204 in reply to: ↑ 195 Changed 5 years ago by
comment:205 Changed 5 years ago by
 Commit changed from 39ee52d817c0b10ad5795cc2b138a4a83475fc25 to 4bcf7dc9ee28539f166c14f973f26401ceb39de3
comment:206 in reply to: ↑ 188 Changed 5 years ago by
Replying to ncohen:
Since most of the internal state is contained in attributes like
self.rho
, you should document what these mean (and# list of current search ranges
is not sufficient documentation).+1 to that. This terminology made it much harder for me to understand what the code was doing. Instead of writing this in the code:
self.rho = [] # list of current search ranges self.mu = [] # list of integers self.j = 1 # index of last element of mu self.nu = 0 # sum of values in muIt would probably be clearer to rename those variables (respectively) as
self._search_range self._current_list self._j self._current_sum
Fixed.
New commits:
fd645e4  17979 changed names of iterator attributes

39ee52d  17979: proper specification of the trailing zeroes 'feature'

4bcf7dc  Merge branch 'public/ticket/17979' of git://trac.sagemath.org/sage into public/ticket/17979

comment:207 in reply to: ↑ 197 Changed 5 years ago by
Replying to jdemeyer:
However, I think it's best if the behaviour of
__contains__
really matches the iterator.
If you take upon you the responsibility of this backward incompatible
change of __contains__
, I'll go for it. Otherwise, I'd rather not
change this now.
I do think that, by default, we shouldn't output lists with trailing zeros, since this will lead in many cases to infinitely many lists satisfying the constraints.
Yeah, that was my original motivation too.
If you ever allow negative parts, then the convention of having no trailing zeros becomes very strange, since "nonzero" is no longer a convex condition.
Yup, one more can of worms.
In #17920 I solved this by setting a minimum/maximum value for the last part of a list, if the list is longer than
min_length
. By default, this minimum is 1 with no maximum which gives the same lists as the "identify trailing zeros" convention.
I definitely prefer this approach. This is also why I hesitated having
min_part
take precedence over floor=[...]
, for otherwise you could
just do floor=[1,1,0,3], min_part=1
. Well, it's still possible to
achieve this through a floor function but if the limit of the function
is not specified, the code can't decide certain things.
Anyway, let's keep the "feature" for now, and take care of it in a later ticket in a consistent way with #17920.
Cheers,
Nicolas
New commits:
fd645e4  17979 changed names of iterator attributes

4bcf7dc  Merge branch 'public/ticket/17979' of git://trac.sagemath.org/sage into public/ticket/17979

comment:208 in reply to: ↑ 180 ; followup: ↓ 214 Changed 5 years ago by
Replying to jdemeyer:
I agree with this comment:
.. TODO:: Maybe this should be ``check=False`` instead?The standard terminology for such an option is indeed
check=False
andwaiver
appears only ininteger_list.py
.
The thing is that there really are two different use cases here:
(1) I know what I am doing, you do not need to check my input.
(2) I know what I am doing, don't show me again this warning when
accessing the more tricky features.
The first use case definitely fits within the usual check=False
terminology. I am not so sure about the second one. In fact, I could
imagine situations where I would want (2) without (1): "I'll be using
the tricky features, still double check everything you can".
But maybe it's not worth the additional API complexity, and everything
should just fall into check=False
. Or rename "waiver=..." to
warnings=False
. I don't have a strong opinion.
Cheers,
Nicolas
comment:209 in reply to: ↑ 190 ; followup: ↓ 213 Changed 5 years ago by
Replying to jdemeyer:
I would also prefer to remove the text concerning algorithmic complexity in
src/sage/combinat/tutorial.py
. What I dislike most is that it seems to hide behind the "degenerate cases" exception without really specifying what that means.
Well, defining precisely the "degenerate cases" is a little research project by itself :) But the point is that, in most practical use cases, the complexity is low (or will be low once an improved lookahead will be implemented #18055). I am happy to reformulate it this way if you prefer. But I'd rather keep some short sentence about this topic here, as it explains the rationale of the approach to the reader.
comment:210 Changed 5 years ago by
 Commit changed from 4bcf7dc9ee28539f166c14f973f26401ceb39de3 to 49dd343182197e2707cf30d5fa118bafede16769
Branch pushed to git repo; I updated commit sha1. New commits:
49dd343  17979 debugging Jeroen's example; added doc test that catches the hang

comment:211 in reply to: ↑ 203 ; followup: ↓ 284 Changed 5 years ago by
Replying to nthiery:
Replying to jdemeyer:
Please add this somewhere in
__init__
:if min_length < 0: min_length = 0I am not sure whether I prefer this, or barking, but that's fine. Done, together with further typechecks.
Well, I also prefer raise ValueError(...)
in this case, but some partitions code really sends a negative value for min_length
to IntegerListsLex
.
comment:212 followup: ↓ 223 Changed 5 years ago by
Concerning type checks: instead of x in ZZ
, it's better to simply convert to a known type: use x = ZZ(x)
instead (or see my function integer_or_infinity()
in #17920).
comment:213 in reply to: ↑ 209 ; followup: ↓ 237 Changed 5 years ago by
Replying to nthiery:
But I'd rather keep some short sentence about this topic here, as it explains the rationale of the approach to the reader.
Fine, I understand your point. However, I think it should perhaps be phrased in a more informal way. Since you talk about polynomialtime, it sounds like the statement of some mathematical theorem, but it isn't.
You can just say something like "it's fast in practice for simple examples".
comment:214 in reply to: ↑ 208 ; followups: ↓ 226 ↓ 235 Changed 5 years ago by
Replying to nthiery:
(1) I know what I am doing, you do not need to check my input.
(2) I know what I am doing, don't show me again this warning when
accessing the more tricky features.
To be honest, I don't think there is much difference between these two. Suppose hypothetically that we would add two different flags for (1) and (2), which checks would be controlled by (1) and which by (2)?
I prefer the name check=False
mainly because it's very standard in Sage.
comment:215 Changed 5 years ago by
 Commit changed from 49dd343182197e2707cf30d5fa118bafede16769 to 3630fb51346d426a75ea0991027663e003185157
Branch pushed to git repo; I updated commit sha1. New commits:
3630fb5  17979: fixed hang in _possible_m

comment:216 in reply to: ↑ 191 Changed 5 years ago by
Replying to jdemeyer:
This hangs:
sage: list(IntegerListsLex(1, min_length=2, min_slope=0, max_slope=0))(it works fine without the
min_length
though)
Thank you for catching this! It should be fixed now! There was a wrong variable in _possible_m.
comment:217 Changed 5 years ago by
 Commit changed from 3630fb51346d426a75ea0991027663e003185157 to 3356cc375a40ddbff4efc8d1e76512ba027a25de
Branch pushed to git repo; I updated commit sha1. New commits:
3356cc3  17979: fixed hang in _possible_m: inserted original test from trac

comment:218 in reply to: ↑ 191 Changed 5 years ago by
Replying to jdemeyer:
This hangs:
sage: list(IntegerListsLex(1, min_length=2, min_slope=0, max_slope=0))(it works fine without the
min_length
though)
You really are shaking this guy out! That's good :)
We looked this up with Anne and the hang was in ._possible_m
; the issue was similar to one we had elsewhere: if the ceiling is 0 at some point and max_slope=0, then we know this should be treated as if there was a ceiling limit of 0. In fact, this was already tested, but not on a moving position; so this was a 1 character fix at the end.
I'll document this method in detail later today.
comment:219 Changed 5 years ago by
 Commit changed from 3356cc375a40ddbff4efc8d1e76512ba027a25de to a962d5bcc024dd87caf98c8e2657137ef7582ed1
Branch pushed to git repo; I updated commit sha1. New commits:
a962d5b  17979: work on the documentation of _possible_m

comment:220 Changed 5 years ago by
 Commit changed from a962d5bcc024dd87caf98c8e2657137ef7582ed1 to 13b7a803b96e3b73a8bf1cd986d46f1ad8e1e89c
Branch pushed to git repo; I updated commit sha1. New commits:
13b7a80  17979: Improved documentation of internal function + some code cleaning there

comment:221 Changed 5 years ago by
 Commit changed from 13b7a803b96e3b73a8bf1cd986d46f1ad8e1e89c to 49664f7bf16bb05f507398998ef5ac72ec9d071a
Branch pushed to git repo; I updated commit sha1. New commits:
49664f7  17979 change x in ZZ to x = ZZ(x)

comment:222 Changed 5 years ago by
 Commit changed from 49664f7bf16bb05f507398998ef5ac72ec9d071a to f102509c1c5d59632acfa7caf811104baf70fb6f
Branch pushed to git repo; I updated commit sha1. New commits:
f102509  17979 more x=ZZ(x)

comment:223 in reply to: ↑ 212 Changed 5 years ago by
comment:224 Changed 5 years ago by
 Commit changed from f102509c1c5d59632acfa7caf811104baf70fb6f to 43100fa2cd1a03747089c9be9890fcaa0040f7de
comment:225 Changed 5 years ago by
 Commit changed from 43100fa2cd1a03747089c9be9890fcaa0040f7de to 422d972596908dfa24dd4ff90ba71ae891abb9d1
Branch pushed to git repo; I updated commit sha1. New commits:
422d972  17979 switched waiver to check

comment:226 in reply to: ↑ 214 Changed 5 years ago by
Replying to jdemeyer:
Replying to nthiery:
(1) I know what I am doing, you do not need to check my input.
(2) I know what I am doing, don't show me again this warning when
accessing the more tricky features.
To be honest, I don't think there is much difference between these two. Suppose hypothetically that we would add two different flags for (1) and (2), which checks would be controlled by (1) and which by (2)?
I prefer the name
check=False
mainly because it's very standard in Sage.
Fixed!
comment:227 Changed 5 years ago by
 Commit changed from 422d972596908dfa24dd4ff90ba71ae891abb9d1 to 4b0f3d983b1284bbab73c91f5aadbc52872f60fb
Branch pushed to git repo; I updated commit sha1. New commits:
4b0f3d9  17979 made all attributes private

comment:228 Changed 5 years ago by
 Commit changed from 4b0f3d983b1284bbab73c91f5aadbc52872f60fb to 0fe6dcd962a734b21e49cd58a7e56c3ec664bf8f
Branch pushed to git repo; I updated commit sha1. New commits:
0fe6dcd  17979 small doc fixes

comment:229 Changed 5 years ago by
 Commit changed from 0fe6dcd962a734b21e49cd58a7e56c3ec664bf8f to 93ad012c301ab9b565080d336378cc0edef6ff9a
comment:230 Changed 5 years ago by
 Description modified (diff)
comment:231 Changed 5 years ago by
 Commit changed from 93ad012c301ab9b565080d336378cc0edef6ff9a to b2b30103f152d8c4a3ea566b8a436153e2b07afb
Branch pushed to git repo; I updated commit sha1. New commits:
b2b3010  17979: added test from the http://wiki.sagemath.org/combinat/Weirdness

comment:232 Changed 5 years ago by
 Commit changed from b2b30103f152d8c4a3ea566b8a436153e2b07afb to 37ae5e48a5448def4b76a5b4d38baa9c3cb7e9b4
Branch pushed to git repo; I updated commit sha1. New commits:
37ae5e4  17979: added link to IntegerListsLex in the 'enumerated sets' index of the reference manual

comment:233 Changed 5 years ago by
 Commit changed from 37ae5e48a5448def4b76a5b4d38baa9c3cb7e9b4 to 7e9c0b6c1b1e6e26422e6a0238880d4cdcc5ef34
comment:234 Changed 5 years ago by
 Commit changed from 7e9c0b6c1b1e6e26422e6a0238880d4cdcc5ef34 to dba4c6233d2af762986501528370c84c1d24736a
comment:235 in reply to: ↑ 214 Changed 5 years ago by
Replying to jdemeyer:
To be honest, I don't think there is much difference between these two. Suppose hypothetically that we would add two different flags for (1) and (2), which checks would be controlled by (1) and which by (2)?
Well, I would know, but you are probably right: let's keep it simple for the user.
comment:236 Changed 5 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
comment:237 in reply to: ↑ 213 Changed 5 years ago by
Replying to jdemeyer:
Fine, I understand your point. However, I think it should perhaps be phrased in a more informal way. Since you talk about polynomialtime, it sounds like the statement of some mathematical theorem, but it isn't.
You can just say something like "it's fast in practice for simple examples".
Ok. Fast being very vague I tried to reformulate this, as well as the
comment on the complexity in IntegerListsLex
, to be less formal
while still giving some useful indication to the reader.
I very much hope that at some point we will be able to replace this by precise complexity information, at least within well defined cases.
comment:238 Changed 5 years ago by
 Commit changed from dba4c6233d2af762986501528370c84c1d24736a to ac1365cdf11ed413a3e534594176cd24fe75cabd
Branch pushed to git repo; I updated commit sha1. New commits:
ac1365c  17979: improved _search_range > _search_ranges; IntegerListsLex._IntegerListLexIter > IntegerListsLex._Iter + micro doc improvement

comment:239 Changed 5 years ago by
Ok, we believe we took care of all the comments here, hence back to
needs review. Anne had a first look at the changes in
integer_vectors
, and Travis will double check probably on Monday.
I have been trough the internal documentation, and spent quite some time improving it. It could be further improved. Yet, it's probably best not to spend too much time on it either, since it's likely to get updated once better look ahead are implemented.
New commits:
ac1365c  17979: improved _search_range > _search_ranges; IntegerListsLex._IntegerListLexIter > IntegerListsLex._Iter + micro doc improvement

comment:240 followup: ↓ 251 Changed 5 years ago by
 Status changed from needs_review to needs_work
sage: L = IntegerListsLex(length=2, max_part=0) sage: [0,0] in L True sage: L.list() []
comment:241 followup: ↓ 252 Changed 5 years ago by
I think this input should be allowed:
sage: IntegerListsLex(7, min_slope=Infinity).list()
comment:242 Changed 5 years ago by
This list is obviously finite:
sage: L = IntegerListsLex(max_part=1, min_slope=10) sage: L.list() ... ValueError: The specified parameters do not allow for an inverse lexicographic iterator
comment:243 Changed 5 years ago by
The following are also very clearly finite (but still ValueError
):
sage: L = IntegerListsLex(length=0) sage: L = IntegerListsLex(max_length=0, min_length=1)
comment:244 Changed 5 years ago by
Also this one:
sage: L = IntegerListsLex(min_sum=10, max_sum=5)
comment:245 Changed 5 years ago by
 Commit changed from ac1365cdf11ed413a3e534594176cd24fe75cabd to 5cc08d541980a52c41eb22203659f779be291e36
Branch pushed to git repo; I updated commit sha1. New commits:
5cc08d5  17979: added tests for _check_lexicographic_iterable from Jeroen

comment:246 Changed 5 years ago by
 Commit changed from 5cc08d541980a52c41eb22203659f779be291e36 to a005d80a7b123ecee62da097a9c93a94da241e8c
Branch pushed to git repo; I updated commit sha1. New commits:
a005d80  17979 fixed bounded region cases

comment:247 Changed 5 years ago by
 Commit changed from a005d80a7b123ecee62da097a9c93a94da241e8c to 6de41768a385f5742dd72eed35746cd5ca22afc9
Branch pushed to git repo; I updated commit sha1. New commits:
6de4176  17919: take the enveloppe of the ceiling and floor when they are lists (yields better look ahead and value error detection)

comment:248 followup: ↓ 256 Changed 5 years ago by
 Reviewers changed from Nathann Cohen, Jeroen Demeyer to Nathann Cohen, Jeroen Demeyer, Travis Scrimshaw
Here are my comments on the current state of things:
 In
integer_list.py
: I don't understand this sentence in the header: "It was then completely rewritten in 2015 by Gillespie, Schilling, and Thiery, with the help of many, to catter for limitations and lack of robustness w.r.t. input." I think by "catter" you mean "cater", but that isn't correct usage of the word.
 "dyck words" capitalization.
 I don't like the fact that when the answer is known to be infinite, that the category is
FiniteEnumeratedSets
.  You should test also when the input
n
is a tuple.  In
_check_lexicographic_iterable
, "Checks" should be "Check"
 In
tutorial.py
,predict when a sequence `\ell_0,\dot,\ell_k` is a prefix of some
, it should be "\dots".
 In
integer_vector.py
 Use absolute paths instead of relative paths:
from combinat import CombinatorialClass
 In
list2func
, could we codeafy the doc?  In the
__init__
, this is missing the doublecolon: "All the attributes below are private; don't use them!"  Could we split the long line in the
_repr_
?  Should we formally deprecate the
next
method?  In the error message "If k is a list, no optional argument is supported", let's make it lowercase.
 Use absolute paths instead of relative paths:
Otherwise I'm okay with how the code looks (but I did not run tests like Jeroen).
comment:249 Changed 5 years ago by
 Commit changed from 6de41768a385f5742dd72eed35746cd5ca22afc9 to 4e96d307a311f37312aa5b161d12e48c8348d668
Branch pushed to git repo; I updated commit sha1. New commits:
4e96d30  17979: reworked the logic of _possible_m to make it clearer

comment:250 Changed 5 years ago by
 Commit changed from 4e96d307a311f37312aa5b161d12e48c8348d668 to 48cbd1f2ca8d6e1fd73f8e6dad0a94c4b987ba3b
Branch pushed to git repo; I updated commit sha1. New commits:
48cbd1f  17979: fixed Iter._possible_m

comment:251 in reply to: ↑ 240 Changed 5 years ago by
comment:252 in reply to: ↑ 241 ; followup: ↓ 253 Changed 5 years ago by
Replying to jdemeyer:
I think this input should be allowed:
sage: IntegerListsLex(7, min_slope=Infinity).list()
Hmm, this would be generating lists of length at most 1.
Do you see any real use case?
It seems to me that the specification that min_slope
is either oo
or an integer (and symmetrically for max_slope
) is quite natural,
and allowing for +oo
would only mean adding more special cases and
complications to handle for no added value.
Cheers,
Nicolas
Btw: thanks for all the interesting corner cases you posted!
comment:253 in reply to: ↑ 252 ; followup: ↓ 259 Changed 5 years ago by
Replying to nthiery:
Do you see any real use case?
I certainly have no use case. It just seems a bit strange to allow every possible value for min_slope
except +Infinity
.
At least make it a ValueError
if min_slope=Infinity
or max_slope=Infinity
is given.
comment:254 Changed 5 years ago by
 Commit changed from 48cbd1f2ca8d6e1fd73f8e6dad0a94c4b987ba3b to 126c9e7cb7dac2a9f2c66708125b2385ff9b4b3b
Branch pushed to git repo; I updated commit sha1. New commits:
126c9e7  17979 addressed Travis' comments

comment:255 Changed 5 years ago by
 Commit changed from 126c9e7cb7dac2a9f2c66708125b2385ff9b4b3b to 3a8f47a93266b82928539304ae21212e9885716f
Branch pushed to git repo; I updated commit sha1. New commits:
6f3f524  Revert "17919: take the enveloppe of the ceiling and floor when they are lists (yields better look ahead and value error detection)"

f14c8cc  17919: added tests and documentation to _m_interval; fixed typo

3a8f47a  Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

comment:256 in reply to: ↑ 248 ; followup: ↓ 257 Changed 5 years ago by
Replying to tscrim:
Here are my comments on the current state of things:
Travis' comments are fixed now. Here are some further responses:
 I don't like the fact that when the answer is known to be infinite, that the category is
FiniteEnumeratedSets
.
When IntegerListsLex? is enumerable (i.e. the vectors can be iterated over in inverse lex order), then the list is finite. We will explain this in the code.
 Should we formally deprecate the
next
method?
No, since the plan is to implement this later, so there is no need to deprecate it now.
New commits:
6f3f524  Revert "17919: take the enveloppe of the ceiling and floor when they are lists (yields better look ahead and value error detection)"

f14c8cc  17919: added tests and documentation to _m_interval; fixed typo

3a8f47a  Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

comment:257 in reply to: ↑ 256 Changed 5 years ago by
Replying to aschilling:
When IntegerListsLex? is enumerable (i.e. the vectors can be iterated over in inverse lex order), then the list is finite. We will explain this in the code.
Oh, actually not quite. Sorry, my bad. I applied Koenig's lemma to quick. The equivalence finite <=> inverse lexicographically enumerable is almost true, except for extreme cases like:
sage: IntegerListsLex(n=1) > [1], [0,1], [0,0,1] ...
We will think about this a bit more and update the code accordingly.
comment:258 Changed 5 years ago by
 Commit changed from 3a8f47a93266b82928539304ae21212e9885716f to 9278051dd34ba2c5967ef191d0c9ca9e124275cf
Branch pushed to git repo; I updated commit sha1. New commits:
9278051  17979: type checking on min_slope and max_slope

comment:259 in reply to: ↑ 253 Changed 5 years ago by
Replying to jdemeyer:
Replying to nthiery:
Do you see any real use case?
I certainly have no use case. It just seems a bit strange to allow every possible value for
min_slope
except+Infinity
.At least make it a
ValueError
ifmin_slope=Infinity
ormax_slope=Infinity
is given.
Oh, I see your point now. I somehow thought this was already checked for. Done now: if min_slope
is not oo
, then it's converted to an integer. Thanks.
comment:260 Changed 5 years ago by
 Commit changed from 9278051dd34ba2c5967ef191d0c9ca9e124275cf to f3b5a70855c6bc80c83f0967006ecfcc9a811140
Branch pushed to git repo; I updated commit sha1. New commits:
f3b5a70  17979: further renamed local variables

comment:261 followup: ↓ 264 Changed 5 years ago by
I know this hasn't been set back to needs_review, but just as a reminder:
OSError: [combinat ] /usr/local/src/sageconfig/local/lib/python2.7/sitepackages/sage/combinat/integer_list.py:docstring of sage.combinat.integer_list.IntegerListsLex:9: WARNING: Inline literal startstring without endstring.
comment:262 Changed 5 years ago by
 Commit changed from f3b5a70855c6bc80c83f0967006ecfcc9a811140 to e06c09eba54005807aeff9e056ee4ff150596c20
Branch pushed to git repo; I updated commit sha1. New commits:
e06c09e  17979: reworked the logic of next and push_search; this fixes the handling of length=0

comment:263 Changed 5 years ago by
 Commit changed from e06c09eba54005807aeff9e056ee4ff150596c20 to d36d0e7d5819e94e1e6ffb011f0f52460e5cb5a6
Branch pushed to git repo; I updated commit sha1. New commits:
d36d0e7  17979: fixed ReST typo, and started reworking the discussion about finiteness

comment:264 in reply to: ↑ 261 Changed 5 years ago by
Replying to jdemeyer:
I know this hasn't been set back to needs_review, but just as a reminder:
OSError: [combinat ] /usr/local/src/sageconfig/local/lib/python2.7/sitepackages/sage/combinat/integer_list.py:docstring of sage.combinat.integer_list.IntegerListsLex:9: WARNING: Inline literal startstring without endstring.
Fixed, thanks!
New commits:
d36d0e7  17979: fixed ReST typo, and started reworking the discussion about finiteness

New commits:
d36d0e7  17979: fixed ReST typo, and started reworking the discussion about finiteness

comment:265 Changed 5 years ago by
 Description modified (diff)
comment:266 followup: ↓ 279 Changed 5 years ago by
Suggestion: use the function is_trivially_zero
from #17920 and don't raise ValueError
(for infinite ceiling or noninverselexicographicallyenumerable) if this returns True
.
comment:267 followups: ↓ 269 ↓ 283 Changed 5 years ago by
After some more testing, I wasn't able to find any more cases of wrong output or hangs.
However, the are many cases where a ValueError
is raised despite the fact that only finitely many lists satisfy the constraints.
Perhaps the exception The specified parameters do not allow for an inverse lexicographic iterator
should be weakened to it looks like the specified parameters do not allow for an inverse lexicographic iterator
or something.
comment:268 Changed 5 years ago by
 Commit changed from d36d0e7d5819e94e1e6ffb011f0f52460e5cb5a6 to 715dc67379dadab0e77c1c5aaa354e3eab0c256b
Branch pushed to git repo; I updated commit sha1. New commits:
715dc67  17979 weakened the noiterator message plus trivial doc changes

comment:269 in reply to: ↑ 267 Changed 5 years ago by
Replying to jdemeyer:
After some more testing, I wasn't able to find any more cases of wrong output or hangs.
However, the are many cases where a
ValueError
is raised despite the fact that only finitely many lists satisfy the constraints.Perhaps the exception
The specified parameters do not allow for an inverse lexicographic iterator
should be weakened toit looks like the specified parameters do not allow for an inverse lexicographic iterator
or something.
Yes, I agree with this and changed the message. Jeroen, you are doing a very detailed review of the code and its functioning. It is very helpful! Thank you!
comment:270 Changed 5 years ago by
 Commit changed from 715dc67379dadab0e77c1c5aaa354e3eab0c256b to 04a620591cae0412dc0ed6c39666891e46876459
Branch pushed to git repo; I updated commit sha1. New commits:
04a6205  17979 explained iterable versus finiteness issue; changed message accordingly

comment:271 Changed 5 years ago by
 Description modified (diff)
comment:272 Changed 5 years ago by
 Commit changed from 04a620591cae0412dc0ed6c39666891e46876459 to fa3790140fc5fe801ef3c49a36afbeab98283a79
Branch pushed to git repo; I updated commit sha1. New commits:
fa37901  17979 paramter>constraint and .parent > ._parent

comment:273 followup: ↓ 278 Changed 5 years ago by
Could you please document the new algorithm somewhere ? I downloaded the branch again today and had no idea what the values "decreasing, push, pop, me" actually meant O_o
Nathann
comment:274 Changed 5 years ago by
 Commit changed from fa3790140fc5fe801ef3c49a36afbeab98283a79 to 00b01087a6afdb118d68d87b9264f021432b8f59
Branch pushed to git repo; I updated commit sha1. New commits:
00b0108  17979: extracted a separate class to handle envelopes

comment:275 Changed 5 years ago by
 Commit changed from 00b01087a6afdb118d68d87b9264f021432b8f59 to 1d5ab6bfb820219c7929fad164079cf6f5b12ed3
Branch pushed to git repo; I updated commit sha1. New commits:
1d5ab6b  17917: proofread discussion about finiteness

comment:276 Changed 5 years ago by
 Commit changed from 1d5ab6bfb820219c7929fad164079cf6f5b12ed3 to 4b2f96bf0a032c069ec0240af8e8938926a9990c
Branch pushed to git repo; I updated commit sha1. New commits:
4b2f96b  17979: added documentation about the different states for the iteration

comment:277 Changed 5 years ago by
 Description modified (diff)
comment:278 in reply to: ↑ 273 Changed 5 years ago by
Replying to ncohen:
Could you please document the new algorithm somewhere ? I downloaded the branch again today and had no idea what the values "decreasing, push, pop, me" actually meant
O_o
Done!
It's in fact the same algorithm as before; just trying to better highlight the structure, and reorganizing it to fix the logic for the corner case of length 0 (fixes comment:243).
Cheers,
comment:279 in reply to: ↑ 266 Changed 5 years ago by
Replying to jdemeyer:
Suggestion: use the function
is_trivially_zero
from #17920 and don't raiseValueError
(for infinite ceiling or noninverselexicographicallyenumerable) if this returnsTrue
.
I must admit that I have been focusing on getting this ticket done, at the price of looking at the details of your ticket right now ... So thanks much for your pointers; that's helpful!
In this specific case, it turns out that it's really the logic that
had to be fixed, and I won't need is_trivially_zero
.
Cheers,
Nicolas
comment:280 Changed 5 years ago by
 Commit changed from 4b2f96bf0a032c069ec0240af8e8938926a9990c to a14ed209e342f8e942393ec554a27530dfc3ee34
Branch pushed to git repo; I updated commit sha1. New commits:
a14ed20  17979 doc clean up

comment:281 Changed 5 years ago by
 Commit changed from a14ed209e342f8e942393ec554a27530dfc3ee34 to 4b923e15fddaac5751595717e91bb154b493c638
comment:282 Changed 5 years ago by
 Commit changed from 4b923e15fddaac5751595717e91bb154b493c638 to a939fd59bfcf043bce3c9a61ae072337961873da
Branch pushed to git repo; I updated commit sha1. New commits:
a939fd5  17979: fixed typos in the documentation

comment:283 in reply to: ↑ 267 Changed 5 years ago by
Replying to jdemeyer:
However, the are many cases where a
ValueError
is raised despite the fact that only finitely many lists satisfy the constraints.
With the forward smoothing and partial backward smoothing of the
envelope w.r.t. min_slope
and max_slope
the situation should be
better now. At least all the examples your provided work smoothly,
and I am not sure I have an example under hand that would be finite
and not detected as such.
Perhaps the exception
The specified parameters do not allow for an inverse lexicographic iterator
should be weakened toit looks like the specified parameters do not allow for an inverse lexicographic iterator
or something.
Yes, until we have something guaranteed, that's the right thing to do.
Cheers,
Nicolas
comment:284 in reply to: ↑ 211 Changed 5 years ago by
Replying to jdemeyer:
Well, I also prefer
raise ValueError(...)
in this case, but some partitions code really sends a negative value formin_length
toIntegerListsLex
.
Gasp. Ok, fair enough :)
comment:285 Changed 5 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
New commits:
fa37901  17979 paramter>constraint and .parent > ._parent

00b0108  17979: extracted a separate class to handle envelopes

1d5ab6b  17917: proofread discussion about finiteness

4b2f96b  17979: added documentation about the different states for the iteration

919076a  17979: added missing docstring to Envelope.__init__

a14ed20  17979 doc clean up

4b923e1  Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

a939fd5  17979: fixed typos in the documentation

Is anybody planning to work on this ticket, or it is just a "somebody should do this" ticket?
You might want to recycle some code of #17920, for example the computation of
floor
andceiling
using the various inputs. Also see that ticket for lots of doctests.