Opened 6 years ago
Last modified 5 years ago
#17979 closed defect
Reimplementation of IntegerListsLex — at Version 98
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:  
Report Upstream:  N/A  Work issues:  
Branch:  public/ticket/17979 (Commits)  Commit:  39d1993d70a837967109be12de261f4f504901cc 
Dependencies:  Stopgaps: 
Change History (98)
comment:1 Changed 6 years ago by
 Priority changed from major to blocker
comment:2 Changed 6 years ago by
comment:3 followup: ↓ 6 Changed 6 years ago by
Some people at Sage Days 64 are planning to work on this. Give us some time!
comment:4 Changed 6 years ago by
 Description modified (diff)
 Keywords days64 added
comment:5 Changed 6 years ago by
 Cc ncohen added
comment:6 in reply to: ↑ 3 ; followups: ↓ 8 ↓ 9 Changed 6 years ago by
comment:7 Changed 6 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 6 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 6 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 6 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 6 years ago by
 Cc vdelecroix added
comment:13 in reply to: ↑ 12 Changed 6 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 6 years ago by
Only twice slower now that it uses +inf instead of infinity. infinity really needs to be optimized!
comment:15 Changed 6 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 6 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 6 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 6 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 6 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 6 years ago by
 Commit changed from fb341ea0e6edf9f5958d9d911023c5be201ec9b2 to a3244c09abcea9c9d25fe5043d340692096ccd90
comment:21 Changed 6 years ago by
 Commit changed from a3244c09abcea9c9d25fe5043d340692096ccd90 to e91350397834e04c939029b6677a51da25231194
comment:22 Changed 6 years ago by
 Commit changed from e91350397834e04c939029b6677a51da25231194 to 865a2af4abb9c5a677990c54e435c5d6861f3cf5
comment:23 Changed 6 years ago by
 Commit changed from 865a2af4abb9c5a677990c54e435c5d6861f3cf5 to 6153cf8d39dc23cb41a3d0c2ea66ba5dc3abd2c0
comment:24 Changed 6 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 6 years ago by
 Status changed from new to needs_review
 Work issues set to support n in an iterable
comment:26 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:27 followups: ↓ 28 ↓ 54 ↓ 55 ↓ 65 Changed 6 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 6 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 6 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 6 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 6 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 6 years ago by
There should be empty lines between the bullet points in the INPUT
block.
comment:33 Changed 6 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 6 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 6 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 6 years ago by
Is this really true?
Before trac#17979 the indexing was ambiguous and sometimes started at 1.
comment:37 Changed 6 years ago by
Use newstyle doctest formatting: indent with ....:
instead of ...
comment:38 Changed 6 years ago by
I agree with Nathann that the stuff about timings should be removed.
comment:39 followup: ↓ 70 Changed 6 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 6 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 Changed 6 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 6 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 6 years ago by
comment:44 Changed 6 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 ; followup: ↓ 97 Changed 6 years ago by
comment:46 followup: ↓ 89 Changed 6 years ago by
Remove
from sage.structure.list_clone import ClonableArray from sage.rings.integer import Integer
comment:47 Changed 6 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 6 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 6 years ago by
Replace
raise(Exception("message"))
by
raise Exception("message")
comment:50 followup: ↓ 52 Changed 6 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 6 years ago by
What is IntegerVectors
and why is it not an alias of IntegerListsLex
?
comment:52 in reply to: ↑ 50 ; followup: ↓ 63 Changed 6 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 Changed 6 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 6 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 6 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 followup: ↓ 73 Changed 6 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 6 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 6 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 6 years ago by
What's the point of setting self.floor_type
if you don't use it?
comment:60 Changed 6 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 6 years ago by
Use Infinity
here:
self.floor_limit_start = float('+inf')
comment:62 followup: ↓ 64 Changed 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 6 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 Changed 6 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 6 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 Changed 6 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 6 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 6 years ago by
 Commit changed from 3efcb0a067bb039d28d29b3fd8c9115c18c90d15 to 7b6838c3c12e1144949349bcef3697894d44f66d
comment:88 in reply to: ↑ 40 Changed 6 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 6 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 Changed 6 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 6 years ago by
Replying to aschilling:
Why? ClonableArray? is used!
It was imported twice, but that's already fixed.
comment:92 Changed 6 years ago by
 Commit changed from 7b6838c3c12e1144949349bcef3697894d44f66d to ba68b9d7d80c4c50f124d803f21e3a07b92187d6
comment:93 Changed 6 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 6 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 Changed 6 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 6 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 6 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 6 years ago by
 Description modified (diff)
 Work issues support n in an iterable deleted
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.