Reimplementation of IntegerListsLex

[aschilling]

As documented in #17548, #17956, there are several bugs in IntegerListsLex which also have implications for !Partitions and !Compositions. This branch reimplements IntegerListsLex.

Follow-ups: #18109, #17920, #18055, #18056.

[jdemeyer]

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 and ceiling using the various inputs. Also see that ticket for lots of doctests.

[aschilling]

Some people at Sage Days 64 are planning to work on this. Give us some time!

[jdemeyer]

Replying to aschilling:

Give us some time!

It was a question, not an attack...

[jdemeyer]

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.

[nthiery]

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 side-tracked). 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

[aschilling]

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.

[jdemeyer]

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 correct-but-slow polyhedron implementation, or this ticket needs to be finished.

[nthiery]

Ok, sounds good!

[aschilling]

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.

[nthiery]

Only twice slower now that it uses +inf instead of infinity. infinity really needs to be optimized!

[jdemeyer]

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.

[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).

[aschilling]

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

[jdemeyer]

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.

[aschilling]

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

[git]

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

​f56bd63	Updated documentation of IntegerListsLex to reflect algorithmic changes and added features
​a3244c0	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into public/ticket/17979

[git]

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

​a05b197	17979: doc fix + updated benchmarks
​e913503	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into ticket/17979

[git]

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

​6341435	17979: rest fix
​865a2af	17979: integer vectors are supposed to be lists

[git]

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

​21a1a36	17979 Updated documentation
​ff9e4a2	Updated copyright
​6153cf8	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into public/ticket/17979

[nthiery]

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.

[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 constraints on the lists are as follows: -- in what follows you use a variable l 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 of waiver 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 sage-devel or sage-support 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

[jdemeyer]

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.

[ncohen]

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.

[jdemeyer]

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.

[jdemeyer]

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.

[jdemeyer]

There should be empty lines between the bullet points in the INPUT block.

[jdemeyer]

The heading should be formatted like http://www.sagemath.org/doc/developer/coding_basics.html#headings-of-sage-library-code-files (in particular, it's bad to mention the GPL without version number).

[jdemeyer]

Why do you want to supporting floor and ceiling being a number? We already have min_part and max_part for that.

[jdemeyer]

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

[jdemeyer]

Is this really true?

Before trac#17979 the indexing was ambiguous and sometimes started at 1.

[jdemeyer]

Use new-style doctest formatting: indent with ....: instead of ...

[jdemeyer]

I agree with Nathann that the stuff about timings should be removed.

[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!

[jdemeyer]

This takes forever, even though the list trivially contains just one element:

sage: IntegerListsLex(10^100, max_length=1).list()

[jdemeyer]

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.

[jdemeyer]

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.

[jdemeyer]

Note that this example is instant with #17920:

sage: IntegerLists(10^100, max_length=1).list()

[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()

[jdemeyer]

Remove

from sage.structure.list_clone import ClonableArray
from sage.rings.integer import Integer

[jdemeyer]

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

[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/sage-config/local/lib/python2.7/site-packages/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.

[jdemeyer]

Replace

raise(Exception("message"))

by

raise Exception("message")

[jdemeyer]

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.

[jdemeyer]

What is IntegerVectors and why is it not an alias of IntegerListsLex?

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

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

[jdemeyer]

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.

[jdemeyer]

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.

[jdemeyer]

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.

[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).

[jdemeyer]

There are a lot of TODO items in the code and #commented out code which should be cleaned up.

[jdemeyer]

Errors like these should be TypeError instead of ValueError:

raise(ValueError("unable to parse value of min_part"))

[jdemeyer]

What's the point of setting self.floor_type if you don't use it?

[jdemeyer]

This is not a tricky question but still takes forever:

sage: IntegerLists(1, min_part=0, max_part=0).list()

[jdemeyer]

Use Infinity here:

            self.floor_limit_start = float('+inf')

[bgillespie]

Thanks for the thorough comments--Nicolas, 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.

[nthiery]

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 not-too-degenerate 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

[nthiery]

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

[bgillespie]

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 variable l 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 raised--in 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 of waiver 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 user-facing; 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 sage-devel or sage-support 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

[git]

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

[bgillespie]

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

[bgillespie]

Replying to jdemeyer:

Why do you want to supporting floor and ceiling being a number? We already have min_part and max_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.

[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.

[bgillespie]

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 specification--none 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 well-ordered). 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.

[bgillespie]

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/sage-config/local/lib/python2.7/site-packages/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.

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 follow--but 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)

[jdemeyer]

Replying to bgillespie:

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.

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

[bgillespie]

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.

[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.

[bgillespie]

Replying to jdemeyer:

Replying to bgillespie:

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.

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

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.

[bgillespie]

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?

[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 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.

[nthiery]

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!

[bgillespie]

Hi Nicolas,

All my current changes are pushed to the ticket--I 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 part-time for the next few days--so 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.

[git]

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

[git]

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

​3efcb0a

17979: Reworked documentation, and updated sage.combinat.tutorial

[ncohen]

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 raised--in 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 user-facing; 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¹⁰ 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

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

1. raise an exception if the iterator doesn't iterate over all elements.
2. drop the "lexicographic order" requirement.

[jdemeyer]

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.

[jdemeyer]

Replying to bgillespie:

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.

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.

[ncohen]

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.

[git]

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

​2b6fcea	17979 fixed large n problem
​6441870	Merge branch 'public/ticket/17979' of git://trac.sagemath.org/sage into public/ticket/17979
​7b6838c	17979 fixed merge

[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.

[aschilling]

Replying to jdemeyer:

Remove

from sage.structure.list_clone import ClonableArray
from sage.rings.integer import Integer

Why? ClonableArray? is used!

[aschilling]

Replying to ncohen:

P.S.: currently, this branch keeps a copy of integer_list.py as integer_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!

[jdemeyer]

Replying to aschilling:

Why? ClonableArray? is used!

It was imported twice, but that's already fixed.

[git]

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

​9593913	17919: simplified and fully documented API for specifying min_part/floor and max_part/ceiling
​ba68b9d	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into ticket/17979

[git]

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

​e036115

17919: infinity -> _infinity

[nthiery]

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 1-based indexing was only used internally in the old IntegerListLex?. I removed that comment.

[nthiery]

Replying to jdemeyer:

What is IntegerVectors and why is it not an alias of IntegerListsLex?

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.

[git]

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

​39d1993

17919: slightly better phrasing

[nthiery]

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.

[ncohen]

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

[ncohen]

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

[nthiery]

Replying to jdemeyer:

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.

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.

[nthiery]

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's Infinity 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.

[nthiery]

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:

1. raise an exception if the iterator doesn't iterate over all elements.
2. 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

[nthiery]

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?

[nthiery]

Replying to jdemeyer:

Replying to bgillespie:

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.

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.

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 parts
• floor 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).

[nthiery]

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, ...

[git]

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

​f8f9a02

17919: imported Jeroen's example from trac

[nthiery]

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,

[jdemeyer]

OSError: [combinat ] /usr/local/src/sage-config/local/lib/python2.7/site-packages/sage/combinat/integer_list.py:docstring of sage.combinat.integer_list.IntegerListsLex:370: WARNING: Literal block expected; none found.

[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.

[jdemeyer]

Replying to nthiery:

That being said, I don't mind changing _infinity to Infinity in the code if you think this won't bring confusion.

I would prefer Infinity.

[jdemeyer]

Replying to nthiery:

At this point, I have settled for:

• min_part to specify a lower bound for all parts
• floor 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.

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.

[jdemeyer]

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()
...

[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__.

[git]

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

​6efe7be	17979: Updated code of class _IntegerListsLexIter to be more clear in the tree search algorithm it uses. Fixed an indexing bug.
​1a1fac1	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into public/ticket/17979

[bgillespie]

The tree traversal code in the iterator class needed some clean-up 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.

[ncohen]

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

[jdemeyer]

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.

[git]

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

​c2705b8

17979: ReST fix + updated doctest

[git]

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

​01ef7db

17979: _infinity -> Infinity

[ncohen]

Let's first fix IntegerLists(Lex), we can remove integer_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

[nthiery]

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.

[nthiery]

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.

[jdemeyer]

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 of IntegerVectors hasn't changed; only its relation to IntegerListsLex.

Perhaps such changes would better be done in a different ticket, it can only increase the changes of this ticket getting merged.

[git]

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

​9bbd9f3	17979 added missing doc tests
​3530b53	Merge branch 'public/ticket/17979' of git://trac.sagemath.org/sage into public/ticket/17979

[nthiery]

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.

[git]

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

​9fced49	17979: _list_function: the lambda now assumes that i is a non negative integer for speed
​8e51e7b	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into ticket/17979

[nthiery]

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.

[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 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.

[nthiery]

Replying to jdemeyer:

OSError: [combinat ] /usr/local/src/sage-config/local/lib/python2.7/site-packages/sage/combinat/integer_list.py:docstring of sage.combinat.integer_list.IntegerListsLex:370: WARNING: Literal block expected; none found.

Fixed.

[git]

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

​03b1c52	17979 put in check about bad iterator
​da793a3	Merge branch 'public/ticket/17979' of git://trac.sagemath.org/sage into public/ticket/17979

[aschilling]

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!

[git]

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

​fcaa99c

17979: added comment to _check_lexicographic_iterable, and inserted example by Jeroen

[ncohen]

Hello !

I still get an error upon "make doc-clean && make doc-html"

OSError: [combinat ] /home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/combinat/integer_list.py:docstring of sage.combinat.integer_list.IntegerListsLex:338: 
WARNING: undefined label: _section-generic-integerlistlex (if the link has no caption the label must precede a section header)

Nathann

[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")

[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 use integer_list_old.py. You will also avoid the conflict with #17927 this way.

[jdemeyer]

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)

[jdemeyer]

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)

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

[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 counter-intuitive 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],
 []]

[bgillespie]

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 use integer_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.

[jdemeyer]

Replying to bgillespie:

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.

I don't quite understand your comment, but my proposal is: on this ticket, fix only IntegerListsLex and leave the rest for follow-up tickets.

[git]

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

​ba6db57

17979 changed ValueError to RuntimeError and lex order to reverse lex order

[aschilling]

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!

[git]

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

​0a80fd4

17979: fixed crosslink

[git]

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

​090a954	17979 also catch RuntimeError in max_sum infinity case!
​56e831a	Merge branch 'public/ticket/17979' of git://trac.sagemath.org/sage into public/ticket/17979

[aschilling]

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.

[git]

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

​709f9cc

17979 added Jeroen's example about trailing zeroes

[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

Nathann

[git]

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

​652a6d5

17979 fixed doc compilation issue

[aschilling]

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 counter-intuitive 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!

[aschilling]

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

[aschilling]

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.

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

[jdemeyer]

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)

[bgillespie]

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 feature-ful 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.

[git]

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

​ae225b3

17979: reverse lexicographic -> inverse lexicographic

[aschilling]

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

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

[git]

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

​ee740ea	Merge branch 'develop' into public/ticket/17979
​0c5305c	Merge branch 'public/ticket/17979' of git://trac.sagemath.org/sage into public/ticket/17979

[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 the ValueError category: "when a built-in 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

[git]

Branch pushed to git repo; I updated commit sha1. 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+

[nthiery]

Replying to jdemeyer:

The heading should be formatted like http://www.sagemath.org/doc/developer/coding_basics.html#headings-of-sage-library-code-files (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 sage-devel 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+

[nthiery]

Replying to jdemeyer:

It think it is quite trivial to split it up, just make IntegerVectors use integer_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.

[nthiery]

Replying to ncohen:

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.

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

[jdemeyer]

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)

[git]

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

​46d01a9

17979: added Nathann's example of dubious behavior with trailing zeroes

[nthiery]

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

[jdemeyer]

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 the ValueError category: "when a built-in 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.

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.

[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#headings-of-sage-library-code-files. 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 sage-devel and considered ok.

I'd like to see a link to that discussion.

[git]

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

​f634ab0

17979: RuntimeError -> ValueError + fixed message

[nthiery]

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

[git]

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

​ad238f9

17979: formally compliant long copyright header

[nthiery]

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#headings-of-sage-library-code-files. 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

[nthiery]

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

[nthiery]

Replying to jdemeyer:

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.

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.

[git]

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

​9bf94c4	17979: moved min_sum and max_sum later in the __init__ arguments
​f73c43f	17979: trivial doctest fix

[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.

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

[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 and waiver appears only in integer_list.py.

[jdemeyer]

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 non-invlex 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 for IntegerListsLex, Partitions and Compositions (in the other places in Sage where IntegerListsLex 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 in IntegerVectors).

• Speed: for simple examples, #17979 is faster. Both implementations have cases where they behave pathologically: for #17979 this is for example IntegerListsLex(10^10, length=2, min_slope=0, max_slope=0), while #17920 behaves badly if the length gets large.

• Extensibility: because #17920 is based on polyhedra, it will be much easier to generalize the code (it already does some things more general than #17979). Also, if Sage ever gets better Polyhedron code, it will make #17920 faster for free.

[jdemeyer]

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.

[jdemeyer]

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 low-degree polynomial in ``lmax``, where ``lmax`` is
    the length of the longest list. Similarly, the space complexity of
    the algorithm is bounded by a low-degree polynomial in ``lmax``.

(in fact, this statement is probably more true of #17920 than it is for #17979)

[jdemeyer]

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.

[jdemeyer]

This should return the list containg 1 element []:

sage: list(IntegerListsLex(ceiling=[0], max_slope=0))

[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 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 first-hand knowledge of that ^^;

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

[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.

[jdemeyer]

This hangs:

sage: list(IntegerListsLex(1, min_length=2, min_slope=0, max_slope=0))

(it works fine without the min_length though)

[ncohen]

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

[nthiery]

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.

[nthiery]

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 the NOTE about this WARNING.

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

[jdemeyer]

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

[jdemeyer]

Please add this somewhere in __init__:

if min_length < 0:
    min_length = 0

[jdemeyer]

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 "non-zero" 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.

[jdemeyer]

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

[aschilling]

Replying to jdemeyer:

This should return the list containg 1 element []:

sage: list(IntegerListsLex(ceiling=[0], max_slope=0))

This is fixed now!

[git]

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

​31013b9

17979: more checks on length, min_length, max_length

[git]

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

​39ee52d

17979: proper specification of the trailing zeroes 'feature'

[nthiery]

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

[nthiery]

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.

[nthiery]

Replying to jdemeyer:

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

I assume this means that the rest is ok. I updated the documentation accordingly.

[git]

Branch pushed to git repo; I updated commit sha1. 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

[aschilling]

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 mu       

It 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

[nthiery]

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 "non-zero" 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

[nthiery]

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 and waiver appears only in integer_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

[nthiery]

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.

[git]

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

​49dd343

17979 debugging Jeroen's example; added doc test that catches the hang

[jdemeyer]

Replying to nthiery:

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.

Well, I also prefer raise ValueError(...) in this case, but some partitions code really sends a negative value for min_length to IntegerListsLex.

[jdemeyer]

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

[jdemeyer]

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 polynomial-time, 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".

[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.

[git]

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

​3630fb5

17979: fixed hang in _possible_m

[aschilling]

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.

[git]

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

​3356cc3

17979: fixed hang in _possible_m: inserted original test from trac

[nthiery]

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.

[git]

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

​a962d5b

17979: work on the documentation of _possible_m

[git]

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

​13b7a80

17979: Improved documentation of internal function + some code cleaning there

[git]

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

​49664f7

17979 change x in ZZ to x = ZZ(x)

[git]

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

​f102509

17979 more x=ZZ(x)

[aschilling]

Replying to jdemeyer:

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

Fixed!

[git]

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

​84273ab	17979: more informal comments on the complexity of IntegerListsLex in sage.combinat.tutorial
​43100fa	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

[git]

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

​422d972

17979 switched waiver to check

[aschilling]

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!

[git]

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

​4b0f3d9

17979 made all attributes private

[git]

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

​0fe6dcd

17979 small doc fixes

[git]

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

​395f523	17979: reformulated the comment about the complexity, and imported tests from MuPAD-Combinat
​93ad012	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

[git]

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

​b2b3010

17979: added test from the http://wiki.sagemath.org/combinat/Weirdness

[git]

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

[git]

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

​2e9ed34	17979 fixed failing tests in integer_vector
​7e9c0b6	Merge branch 'public/ticket/17979' of git://trac.sagemath.org/sage into public/ticket/17979

[git]

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

​191c8ef	17979: added dyck words / motzkin words examples
​dba4c62	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

[nthiery]

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.

[nthiery]

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 polynomial-time, 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.

[git]

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

[nthiery]

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

[jdemeyer]

sage: L = IntegerListsLex(length=2, max_part=0)
sage: [0,0] in L
True
sage: L.list()
[]

[jdemeyer]

I think this input should be allowed:

sage: IntegerListsLex(7, min_slope=Infinity).list()

[jdemeyer]

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

[jdemeyer]

The following are also very clearly finite (but still ValueError):

sage: L = IntegerListsLex(length=0)
sage: L = IntegerListsLex(max_length=0, min_length=1)

[jdemeyer]

Also this one:

sage: L = IntegerListsLex(min_sum=10, max_sum=5)

[git]

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

​5cc08d5

17979: added tests for _check_lexicographic_iterable from Jeroen

[git]

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

​a005d80

17979 fixed bounded region cases

[git]

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)

[tscrim]

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 code-afy the doc?
  • In the __init__, this is missing the double-colon: "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.

Otherwise I'm okay with how the code looks (but I did not run tests like Jeroen).

[git]

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

​4e96d30

17979: reworked the logic of _possible_m to make it clearer

[git]

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

​48cbd1f

17979: fixed Iter._possible_m

[aschilling]

Replying to jdemeyer:

sage: L = IntegerListsLex(length=2, max_part=0)
sage: [0,0] in L
True
sage: L.list()
[]

Fixed, thanks! We cleaned up _possible_m for this.

---

New commits:

​48cbd1f

17979: fixed Iter._possible_m

[nthiery]

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!

[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 if min_slope=Infinity or max_slope=-Infinity is given.

[git]

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

​126c9e7

17979 addressed Travis' comments

[git]

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

[aschilling]

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

[nthiery]

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.

[git]

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

​9278051

17979: type checking on min_slope and max_slope

[nthiery]

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 if min_slope=Infinity or max_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.

[git]

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

​f3b5a70

17979: further renamed local variables

[jdemeyer]

I know this hasn't been set back to needs_review, but just as a reminder:

OSError: [combinat ] /usr/local/src/sage-config/local/lib/python2.7/site-packages/sage/combinat/integer_list.py:docstring of sage.combinat.integer_list.IntegerListsLex:9: WARNING: Inline literal start-string without end-string.

[git]

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

[git]

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

​d36d0e7

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

[nthiery]

Replying to jdemeyer:

I know this hasn't been set back to needs_review, but just as a reminder:

OSError: [combinat ] /usr/local/src/sage-config/local/lib/python2.7/site-packages/sage/combinat/integer_list.py:docstring of sage.combinat.integer_list.IntegerListsLex:9: WARNING: Inline literal start-string without end-string.

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

[jdemeyer]

Suggestion: use the function is_trivially_zero from #17920 and don't raise ValueError (for infinite ceiling or non-inverse-lexicographically-enumerable) if this returns True.

[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 to it looks like the specified parameters do not allow for an inverse lexicographic iterator or something.

[git]

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

​715dc67

17979 weakened the no-iterator message plus trivial doc changes

[aschilling]

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 to it 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!

[git]

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

​04a6205

17979 explained iterable versus finiteness issue; changed message accordingly

[git]

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

​fa37901

17979 paramter->constraint and .parent -> ._parent

[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

Nathann

[git]

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

​00b0108

17979: extracted a separate class to handle envelopes

[git]

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

​1d5ab6b

17917: proofread discussion about finiteness

[git]

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

​4b2f96b

17979: added documentation about the different states for the iteration

[nthiery]

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,

[nthiery]

Replying to jdemeyer:

Suggestion: use the function is_trivially_zero from #17920 and don't raise ValueError (for infinite ceiling or non-inverse-lexicographically-enumerable) if this returns True.

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

[git]

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

​a14ed20

17979 doc clean up

[git]

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

​919076a	17979: added missing docstring to Envelope.__init__
​4b923e1	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

[git]

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

​a939fd5

17979: fixed typos in the documentation

[nthiery]

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 to it 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

[nthiery]

Replying to jdemeyer:

Well, I also prefer raise ValueError(...) in this case, but some partitions code really sends a negative value for min_length to IntegerListsLex.

Gasp. Ok, fair enough :-)

[aschilling]

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

[nthiery]

For the record:

sage: P = IntegerListsLex(n=40, max_slope=0, min_part=1)
sage: sage: %time x = list(P)
CPU times: user 14.9 s, sys: 23.7 ms, total: 15 s
Wall time: 15 s

This used to be 12s before I introduced the Envelope class. This is due to the fact that we are not using anymore a ConstantFunction? for the floor in this case. We could special case that, but this slow down should disappear as soon as Envelope will be Cythonized, so I'd say that's good enough for now.

Cheers,

Nicolas

[git]

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

​aec1e10

17979: implement Iter.__iter__ to satisfy the iterator protocol

[nthiery]

For the record: with the last commit all long tests pass on sage.math.u-psud.fr (Debian 64 bits)

[jdemeyer]

Replying to nthiery:

I am not sure I have an example under hand that would be finite and not detected as such.

Here are some:

IntegerListsLex(min_sum=1, floor=[1,2], max_part=1).list()
IntegerListsLex(min_length=2, max_length=1).list()

(after more testing, it looks like these are essentially the only examples)

[vdelecroix]

Hello,

There are several things that I do not quite understand. Could you explain or modify it:

1. The iterator IntegerListLex aims to be fast and low-level. What is the point of using the Parent/Element stuff? Why ClonableArray are better than Python lists?

2. Having a nested class seems overkill. The class _Iter is created only once in __iter__. Moreover, all methods in it starts with p = self.parent. Why do you need to create this extra _Iter class? Why does it need to be a nested class?

3. Do you have a use case for

   sage: IntegerListsLex(NN, max_length=3)
   Disjoint union of Lazy family (<lambda>(i))_{i in Non negative integer semiring}
   

   The feature only appears once in the doc in a place which does not appear in the reference manual.

4. Why _check_lexicographic_iterable is a cached method? And I do not get why is it called from _Iter and not at the initialization of IntegerListsLex.

Vincent

[git]

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

​aa89bb2

17979 extra case for finite region

[nthiery]

Salut Vincent!

Thanks for the feedback.

On Tue, Mar 31, 2015 at 12:46:35PM -0000, sage-trac wrote:

There are several things that I do not quite understand. Could you explain or modify it:

1. The iterator IntegerListLex aims to be fast and low-level. What is the point of using the Parent/Element stuff? Why ClonableArray are better than Python lists?

We haven't changed this aspect (in this ticket we focused on refactoring without changing the API): internally, Python lists are used; by default, they are converted to ClonableArray? upon being yielded. The element constructor can be customized to return plain lists if so desired.

In the current state of affairs, this does not really make a difference:

# ClonableArray
sage: L = IntegerListsLex(50, min_part=1, max_slope=0)
sage: it = iter(L)
sage: %timeit x = it.next()
10000 loops, best of 3: 148 µs per loop

# plain lists
sage: L = IntegerListsLex(50, min_part=1, max_slope=0, element_constructor=list)
sage: it = iter(L)
sage: %timeit x = it.next()
10000 loops, best of 3: 134 µs per loop

The overhead comes from the containment test that we do in the check method:

# ClonableArray, with check made trivial
sage: sage: L = IntegerListsLex(50, min_part=1, max_slope=0)
sage: sage: it = iter(L)
sage: sage: %timeit x = it.next()
10000 loops, best of 3: 135 µs per loop

I am not sure this containment check is useful. We could just disable it. What do you think?

For the record: using the parent/element protocol does not necessarily cause a large overhead; ClonableArray? is almost as fast as list (timings to be of course taken with a grain of salt given how small values we are speaking about here):

sage: sage: L = IntegerListsLex(50, min_part=1, max_slope=0)
sage: l = range(1000)
sage: %timeit x =list(l)
100000 loops, best of 3: 2.4 µs per loop
sage: c = L.element_class
sage: %timeit x = c(L, l)
100000 loops, best of 3: 2.85 µs per loop

sage: %timeit [x[i] for i in range(100)]
100000 loops, best of 3: 6.84 µs per loop
sage: %timeit [l[i] for i in range(100)]
100000 loops, best of 3: 5.61 µs per loop

In the long run, when IntegerListsLex will be cythonized, the relative situation may change, since we can hope for speedups of 10-100. Note in particular that we most likely will want to use arrays of ints internally; ClonableIntArray might be a good candidate for this. Or just STL vectors.

2. Having a nested class seems overkill. The class _Iter is created only once in __iter__. Moreover, all methods in it starts with `p = self.parent. Why do you need to create this extra _Iter` class? Why does it need to be a nested class?

The class is needed because the iterator has an internal state. So we need to create a separate object for each concurrently running iterator.

I find that using a nested class IntegerListsLex._Iter, rather than IntegerListsLexIter makes the relation between the two classes explicit (_Iter is for internal use for IntegerListsLex?`). It's also consistent with what we do elsewhere (Element, ...). And there is no overhead in doing so.

3. Do you have a use case for

      sage: IntegerListsLex(NN, max_length=3)
      Disjoint union of Lazy family (<lambda>(i))_{i in Non negative integer
    semiring}
   

   The feature only appears once in the doc in a place which does not appear in the reference manual.

It does appear in the reference manual: see section `Input list or iterable for the sum of the main IntegerListLex?` class.

The feature of iterating by increasing sum is certainly useful. Whether we want the above syntactic sugar -- instead of just using DisjointUnionEnumeratedSets? -- is indeed questionable. The feature was already there, so we kept it to not change the API in this ticket.

4. Why _check_lexicographic_iterable is a cached method? And I do not get why is it called from _Iter and not at the initialization of IntegerListsLex.

We discussed this with Jeroen in some earlier comment. Putting it in the iterator let the user create the IntegerListsLex object, even if it's not finite/iterable. This could be useful for other things than iteration, like membership testing or building the corresponding polytopes (once #17920 will be available).

With that, it's natural to cache error-free runs (error runs won't be cached) to not redo the work in later iterator constructions.

Cheers,

Nicolas

[git]

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

​dcbad45

17979: more documentation about the iterator algorithm + make sure an invariant is satisfied

[nthiery]

Replying to jdemeyer:

Replying to nthiery:

I am not sure I have an example under hand that would be finite and not detected as such.

Here are some:

IntegerListsLex(min_sum=1, floor=[1,2], max_part=1).list()
IntegerListsLex(min_length=2, max_length=1).list()

(after more testing, it looks like these are essentially the only examples)

Cool, in the mean time we fixed both of them. We also looked at your is_trivialy_zero function, and we indeed believe that all listed cases there are treated one way or the other.

[vdelecroix]

Replying to nthiery:

Salut Vincent!

Thanks for the feedback.

On Tue, Mar 31, 2015 at 12:46:35PM -0000, sage-trac wrote:

There are several things that I do not quite understand. Could you explain or modify it:

1. The iterator IntegerListLex aims to be fast and low-level. What is the point of using the Parent/Element stuff? Why ClonableArray are better than Python lists?

We haven't changed this aspect (in this ticket we focused on refactoring without changing the API): internally, Python lists are used; by default, they are converted to ClonableArray? upon being yielded. The element constructor can be customized to return plain lists if so desired.

In the current state of affairs, this does not really make a difference:

...

For the record: using the parent/element protocol does not necessarily cause a large overhead; ClonableArray? is almost as fast as list (timings to be of course taken with a grain of salt given how small values we are speaking about here):

I know that it has not changed. If you modify the constructor to return list, the list is copied twice instead of once. I would not call that a solution.

Most importantly, that was not my point. It makes no sense that a plain Python iterator inherit from Parent. It is a question of design, not of timings. The thing is that tuples and lists are the standard Python objects. This is the way the Python module itertools behaves. Ideally, the IntegerListLex should be plainly Python compatible.

The overhead comes from the containment test that we do in the check method:

# ClonableArray, with check made trivial
sage: sage: L = IntegerListsLex(50, min_part=1, max_slope=0)
sage: sage: it = iter(L)
sage: sage: %timeit x = it.next()
10000 loops, best of 3: 135 µs per loop

I am not sure this containment check is useful. We could just disable it. What do you think?

Definitely!

In the long run, when IntegerListsLex will be cythonized, the relative situation may change, since we can hope for speedups of 10-100. Note in particular that we most likely will want to use arrays of ints internally; ClonableIntArray might be a good candidate for this. Or just STL vectors.

Note that in Python 3 there are arrays of int (as in numpy in Python 2):

​https://docs.python.org/3/library/array.html

But I do not think that itertools will use that.

2. Having a nested class seems overkill. The class _Iter is created only once in __iter__. Moreover, all methods in it starts with `p = self.parent. Why do you need to create this extra _Iter` class? Why does it need to be a nested class?

The class is needed because the iterator has an internal state. So we need to create a separate object for each concurrently running iterator.

Right. But why is it nested? It will be a mess with Cythonization.

I find that using a nested class IntegerListsLex._Iter, rather than IntegerListsLexIter makes the relation between the two classes explicit (_Iter is for internal use for IntegerListsLex?`). It's also consistent with what we do elsewhere (Element, ...). And there is no overhead in doing so.

Having two classes in a file called IntegerListLex and IntegerListLexIterator is rather explicit. I am not sure that following the Parent/Element? direction is the best here. As I said before, it would be cool if this file would be Python compatible.

3. Do you have a use case for

      sage: IntegerListsLex(NN, max_length=3)
      Disjoint union of Lazy family (<lambda>(i))_{i in Non negative integer
    semiring}
   

   The feature only appears once in the doc in a place which does not appear in the reference manual.

It does appear in the reference manual: see section `Input list or iterable for the sum of the main IntegerListLex?` class.

The feature of iterating by increasing sum is certainly useful. Whether we want the above syntactic sugar -- instead of just using DisjointUnionEnumeratedSets? -- is indeed questionable. The feature was already there, so we kept it to not change the API in this ticket.

It is reasonable to keep it in the ticket. But what if I do remove it in another ticket?

4. Why _check_lexicographic_iterable is a cached method? And I do not get why is it called from _Iter and not at the initialization of IntegerListsLex.

We discussed this with Jeroen in some earlier comment. Putting it in the iterator let the user create the IntegerListsLex object, even if it's not finite/iterable. This could be useful for other things than iteration, like membership testing or building the corresponding polytopes (once #17920 will be available).

Right. (And counting).

Vincent

[jdemeyer]

Adding extra conditions breaks things:

sage: IntegerListsLex(ceiling=[2], floor=[4]).list()  # good!
[[]]
sage: IntegerListsLex(7, ceiling=[2], floor=[4]).list()
...
ValueError: Could not check that the specified constraints yield a finite set

[jdemeyer]

Similarly:

sage: IntegerListsLex(max_part=0).list()
[[]]
sage: IntegerListsLex(7, max_part=0).list()
...
ValueError: Could not check that the specified constraints yield a finite set

[jdemeyer]

This is one more example which currently does not work:

sage: IntegerListsLex(length=1, max_slope=0, min_slope=1).list()

[git]

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

​3f534ca

17979 moved one of the finiteness tests

[aschilling]

Replying to jdemeyer:

Adding extra conditions breaks things:

sage: IntegerListsLex(ceiling=[2], floor=[4]).list()  # good!
[[]]
sage: IntegerListsLex(7, ceiling=[2], floor=[4]).list()
...
ValueError: Could not check that the specified constraints yield a finite set

Oops, sorry, my mistake. I had put the test in the wrong spot. This part should be fixed now.

[chapoton]

Please use ....: for doctest continuation (see patchbot report)

[git]

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

​224cdcd	17979: avoid a copy if the element constructor is copy safe (list or tuple for now)
​dd90722	17979: disable check for elements
​0b64f4a	17979: avoid a copy if the element constructor is copy safe: added ClonableArray
​00577b0	17979: disable check for elements: better implementation that does not prevent from manually checking elements
​a993265	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

[nthiery]

On Wed, Apr 01, 2015 at 08:15:51AM -0000, sage-trac wrote:

I know that it has not changed.

Then please discuss this in another ticket to not delay this one.

If you modify the constructor to return list, the list is copied

twice instead of once. I would not call that a solution.

It's trivial to introduce a special case to avoid the copy if the element constructor is known to be safe. In fact it's done now.

Most importantly, that was not my point. It makes no sense that a plain Python iterator inherit from Parent. It is a question of design, not of timings. The thing is that tuples and lists are the standard Python objects. This is the way the Python module itertools behaves. Ideally, the IntegerListLex should be plainly Python compatible.

(for the record, the iterator itself does not inherit from Parent).

I would go even further than you: IntegerListsLex? uses nothing specific of Python either. It would be best implemented as a standalone C++ library. It could then be reused by software outside of the Python world, be templated by whatever structure we want to use for the lists, possibly benefit from further low level optimizations (silk, special processor instructions), etc.

But this discussion belongs to later tickets. Here the goal is to get a correct algorithm. The next step is to get an algorithm with reasonably optimal complexity (while further clarifying its structure). And then should come the rewriting in a low level language.

The overhead comes from the containment test that we do in the check method:

# ClonableArray, with check made trivial
sage: sage: L = IntegerListsLex(50, min_part=1, max_slope=0)
sage: sage: it = iter(L)
sage: sage: %timeit x = it.next()
10000 loops, best of 3: 135 µs per loop

I am not sure this containment check is useful. We could just disable it. What do you think?

Definitely!

Done. Easy to revert if anyone is uncomfortable with this.

Right. But why is it nested? It will be a mess with Cythonization.

At the end, it's all about stylistic preference. It's instantaneous to change if/when desired. Whoever will work next on this can change to his own preferred style. I am not discussing this further.

Having two classes in a file called IntegerListLex and IntegerListLexIterator is rather explicit. I am not sure that following the Parent/Element? direction is the best here. As I said before, it would be cool if this file would be Python compatible.

Nested classes are a feature of plain Python, and of many other programming languages. It turns out that Cython does not support them now, but I don't see any theoretical obstruction (and it can be easily emulated).

Altogether I see no compelling reason not to use this feature when it helps better structure the code.

It is reasonable to keep it in the ticket. But what if I do remove it in another ticket?

I don't have an objection if someone takes the responsibility for this backward incompatible change in a later ticket :-)

Or maybe, if the use case emerges, one should actually go the other way round: make it syntactically trivial to have variants of IntegerListsLex?, graded by any or both of the length and size parameters: it's not as generic as DisjointUnionEnumeratedSets?, but this could save on time by sharing quite some stuff between the graded components (e.g. the parsing of the arguments, the upper and lower envelopes, ...).

Cheers,

Nicolas

[git]

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

​56192a9

17979: fixed old continuation string in integer_list_old.py

[nthiery]

Replying to chapoton:

Please use ....: for doctest continuation (see patchbot report)

Fixed, I believe.

[git]

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

​4b4c54e

17979 fixed another case in _check_lexicographic_iterable

[aschilling]

Replying to jdemeyer:

Similarly:

sage: IntegerListsLex(max_part=0).list()
[[]]
sage: IntegerListsLex(7, max_part=0).list()
...
ValueError: Could not check that the specified constraints yield a finite set

Fixed.

[aschilling]

Replying to jdemeyer:

This is one more example which currently does not work:

sage: IntegerListsLex(length=1, max_slope=0, min_slope=1).list()

The current output is correct, isn't it? [Infinity] would be the output in inverse lexicographic order, which results in the error message that m is unbounded.

[jdemeyer]

Replying to aschilling:

Replying to jdemeyer:

This is one more example which currently does not work:

sage: IntegerListsLex(length=1, max_slope=0, min_slope=1).list()

The current output is correct, isn't it? [Infinity] would be the output in inverse lexicographic order, which results in the error message that m is unbounded.

Sorry, I obviously meant

sage: IntegerListsLex(length=2, max_slope=0, min_slope=1).list()

which should have an empty output.

[jdemeyer]

Another case of "adding a constraint break things":

sage: IntegerListsLex(max_sum=1, min_sum=4).list()
[]
sage: IntegerListsLex(max_sum=1, min_sum=4, min_slope=0).list()
...
ValueError: Could not check that the specified constraints yield a finite set

[jdemeyer]

Design comment: the code for Envelope has a lot of duplication because it needs to deal with upper and lower bounds. Instead, I would propose to have Envelope deal only with upper bounds. The Envelope for the lower bound could then be implemented by adding minus signs in the input and output of Envelope.

[jdemeyer]

The code in IntegerListsLex.__init__ could be simplified.

Compare this from #17920:

        if n is not None:
            n = integer_or_infinity(n)
            min_sum = n
            max_sum = n
            # Set self.n, which is not used by IntegerLists_polyhedron,
            # but by some derived classes
            self.n = n

        if length is not None:
            min_length = length
            max_length = length

        if min_length < 0:
            min_length = 0

        self.min_sum = integer_or_infinity(min_sum)
        self.max_sum = integer_or_infinity(max_sum)
        self.min_length = integer_or_infinity(min_length)
        self.max_length = integer_or_infinity(max_length)
        self.min_part = integer_or_infinity(min_part)
        self.max_part = integer_or_infinity(max_part)
        self.min_slope = integer_or_infinity(min_slope)
        self.max_slope = integer_or_infinity(max_slope)

to this from #17979:

        if n is not None:
            n = ZZ(n)
            self._min_sum = n
            self._max_sum = n
        else:
            self._min_sum = min_sum
            self._max_sum = max_sum

        if length is not None:
            length = ZZ(length)
            min_length = length
            max_length = length
        else:
            min_length = ZZ(min_length)
            if min_length < 0:
                min_length = 0
            if max_length != Infinity:
                max_length = ZZ(max_length)
        self._max_length = max_length
        self._min_length = min_length

        if min_slope != -Infinity:
            min_slope = ZZ(min_slope)
        self._min_slope = min_slope
        if max_slope != Infinity:
            max_slope = ZZ(max_slope)
        self._max_slope = max_slope

        min_part = ZZ(min_part)
        if min_part < 0:
            raise NotImplementedError("strictly negative min_part")

        if max_part != Infinity:
            max_part = ZZ(max_part)

[jdemeyer]

The call to _check_lexicographic_iterable should be moved to IntegerListsLex.__iter__

[ncohen]

The global_options is undocumented and is used only there:

if global_options is not None:
    self.global_options = global_options

Also (see Jeroen's message) the following line

if min_length < 0:
    min_length = 0

Can be rewritten as min_length=max(min_length,0).

Nathann

[jdemeyer]

This should either return [] or raise a ValueError saying that min_sum=Infinity is not allowed:

sage: IntegerListsLex(min_sum=Infinity).list()           
...
ValueError: Could not check that the specified constraints yield a finite set

[git]

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

​c9a047c	trac #17979: Move imports to the (only) place in which they are used
​c5f8c92	trac #17979: Replace |l| with sum(l) as it is only used twice

[jdemeyer]

Replying to ncohen:

The global_options is undocumented and is used only there:

if global_options is not None:
    self.global_options = global_options

It is actually used by Partitions. Given that this is not a regression, I don't consider this a problem.

[ncohen]

def _check_lexicographic_iterable(self):
        """
        Check whether the constraints give a finite set.

If this function checks that the constraints give a finite set, could you pick a name for it which reflects it ?

Nathann

[git]

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

​e60c332

trac #17979: Equivalent local rewrite for better readability

[ncohen]

The first lines of _check_lexicographic_iterable are if self._warning or not self._check: return.

It sounds a bit wrong that the check function would do nothing when explicitly asked to. Instead of stopping early in this situation, could you remove those two lines and only call the function when you mean to?

This would give the function its original meaning: check the data.

Note that the function is only called once.

Nathann

[ncohen]

The function _possible_m(self, m, j, min_sum, max_sum) takes four parameters, all of which are attributes of self.

if self._next_state == LOOKAHEAD:
    m = self._current_list[-1]
    if self._possible_m(m, self._j,
       min_sum - (self._current_sum-m),
       max_sum - (self._current_sum-m)):

It would make more sense to me if this function had no arguments at all.

[git]

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

​8e77229

trac #17979: list[:] is faster than copy(l) and harmless comments

[jdemeyer]

Replying to ncohen:

The first lines of _check_lexicographic_iterable are if self._warning or not self._check: return.

It sounds a bit wrong that the check function would do nothing when explicitly asked to. Instead of stopping early in this situation, could you remove those two lines and only call the function when you mean to?

This would give the function its original meaning: check the data.

+1

[git]

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

​24d6494

trac #17979: No need for a STOP state

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

[ncohen]

(my last commit was breaking stuff. I removed it)

[aschilling]

Replying to jdemeyer:

The call to _check_lexicographic_iterable should be moved to IntegerListsLex.__iter__

Why? That breaks a lot of tests.

[aschilling]

Replying to jdemeyer:

Replying to aschilling:

Replying to jdemeyer:

This is one more example which currently does not work:

sage: IntegerListsLex(length=1, max_slope=0, min_slope=1).list()

The current output is correct, isn't it? [Infinity] would be the output in inverse lexicographic order, which results in the error message that m is unbounded.

Sorry, I obviously meant

sage: IntegerListsLex(length=2, max_slope=0, min_slope=1).list()

which should have an empty output.

Even in this case, I think Sage is currently correct, unless you can define what Infinity-Infinity is (which would be used in the slope conditions).

[git]

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

​58dced5

17979 address some review comments

[git]

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

​d66d70d

17979 fixed another corner case

[aschilling]

Replying to jdemeyer:

Another case of "adding a constraint break things":

sage: IntegerListsLex(max_sum=1, min_sum=4).list()
[]
sage: IntegerListsLex(max_sum=1, min_sum=4, min_slope=0).list()
...
ValueError: Could not check that the specified constraints yield a finite set

Fixed.

[jdemeyer]

Replying to aschilling:

Replying to jdemeyer:

The call to _check_lexicographic_iterable should be moved to IntegerListsLex.__iter__

Why?

Because it is really more logical that such a check would happen in the parent before creating the iterator. The iterator should just iterate. The check belongs to the code creating the iterator. Also, the check_finiteness refers a lot to attributes of the parent, which means that it really belongs there.

[jdemeyer]

Replying to aschilling:

Sorry, I obviously meant

sage: IntegerListsLex(length=2, max_slope=0, min_slope=1).list()

which should have an empty output.

Even in this case, I think Sage is currently correct

Sage is indeed correct that there is an infinite upper bound for part[0]. However, my point is that the resulting list is still finite, so this example could work.

unless you can define what Infinity-Infinity is (which would be used in the slope conditions).

I don't see why I would need to define Infinity - Infinity for this. My point is that the set of lists satisfying those constraints is clearly empty.

[jdemeyer]

Replying to git:

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

​58dced5

17979 address some review comments

You literally added just a check for min_sum == Infinity? That's just completely inconsistent with the rest of the code. Please look at IntegerListsLex.__init__. Really, do it. You will agree that it's an ugly mess, see also 317 (which just got worse).

[ncohen]

see also 317 (which just got worse).

And 319 and 326 as well.

Nathann

[nthiery]

Replying to git:

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

​c9a047c

trac #17979: Move imports to the (only) place in which they are used

For the import of plain Python modules, I don't really see the point. It's very unlikely that we will save on Sage startup time. On the other hand, for e.g. import collections, we will pay a (small) penalty each time an IntegerListsLex object is created.

​c5f8c92

trac #17979: Replace |l| with sum(l) as it is only used twice

Agreed for using sum(l) instead of |l| as notation.

On the other hand, I found useful to mention all the relevant parameters on which we will put constraints in the introductory paragraph, even if they are indeed trivial. Please revert if you agree with that.

Cheers,

Nicolas

[git]

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

​64980f5

17979: avoid a copy if the element constructor is copy safe: Oops: added ClonableArray in the correct place now

[git]

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

​b535b54

17979: type checking on min_sum and max_sum

[git]

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

​7d5bad0

17979: type checking on min_sum and max_sum: updated doctests + tiny formating change

[git]

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

​2779051

17979: ._warning -> ._floor_or_ceiling_is_function + make _check_finiteness report an error instead of hanging when the latter is True

[git]

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

​5b32ad4

17979: reinserted deleted comment + minor formating

[git]

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

​d976b20

17979: moved call to _check_finiteness to __iter__

[nthiery]

Replying to ncohen:

The function _possible_m(self, m, j, min_sum, max_sum) takes four parameters, all of which are attributes of self.

if self._next_state == LOOKAHEAD:
    m = self._current_list[-1]
    if self._possible_m(m, self._j,
       min_sum - (self._current_sum-m),
       max_sum - (self._current_sum-m)):

It would make more sense to me if this function had no arguments at all.

I agree that this should eventually become an argument-less look_ahead method that tests if the current list could possibly be a prefix of some valid list.

I would like to postpone this change to #18055 however: anyway this method will need to be rewritten there (in particular to handle an empty current_list), and changing the interface now would require rewriting most of the current tests of _possible_m to construct a bunch of different IntegerListsLex? objects instead of just passing various arguments. Note also that, as specified in the doc, min_sum and max_sum do not exactly match the corresponding attributes: they are bounds on the tail of the list only (agreed, the difference above could be done in _possible_m).

Cheers,

Nicolas

[git]

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

​ffa4d20

17979: simplification in __init__

[nthiery]

Replying to jdemeyer:

The code in IntegerListsLex.__init__ could be simplified.

Done. Thanks for the for #17920' model.

I ended up not using integer_or_infinity: here I prefer to not accept both -oo and +oo when only one makes sense, and having two functions (or one with parameters) seemed like overkill. This is explicit and simple enough:

    self._max_length = ZZ(max_length) if max_length != Infinity else max_length

Cheers,

Nicolas

[nthiery]

Replying to ncohen:

And 319 ...

In 322 Jeroen agreed above that 319 was in fact ok.

[git]

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

​80ad5c8

17979: Fixed corner case of comment:314

[nthiery]

Replying to jdemeyer:

Design comment: the code for Envelope has a lot of duplication because it needs to deal with upper and lower bounds. Instead, I would propose to have Envelope deal only with upper bounds. The Envelope for the lower bound could then be implemented by adding minus signs in the input and output of Envelope.

I am also not so happy about this. I had considered doing something along the lines you propose, and ended up dropping it for now. This is mainly because, in the next step, the main functionality to add will be the computation of the area below the envelope for which we won't have this symmetry anymore. Also, at this point, we are speaking about 5-6 lines of code that are duplicated very locally. Doing the magic would not take much less than this, and the code would be less straightforward. Sooo, well.

[nthiery]

I believe all the comments have been taken care of. Back to needs review!

Nathann: in case you are around, I am roughly in my office until 2pm.

[ncohen]

Hello,

In 322 Jeroen agreed above that 319 was in fact ok.

Many times in the past I had to fix code which accepts a **kwds and did not check that what it contains is actually read. This lead to silent errors or wrong output, and so I see things like global_options as the highway to bugs.

Jeroen noted that this variable is actually used somewhere else, so I guess it probably should not be removed in this ticket. My comment at 319 still need to be adressed, however, as there is no documentation for this parameter. Please make it explain the uses of this flag, possibly by pointing to some other part of the doc if it is already explained somewhere else.

The function _possible_m(self, m, j, min_sum, max_sum) takes four parameters, all of which are attributes of self.

I agree that this should eventually become an argument-less look_ahead method that tests if the current list could possibly be a prefix of some valid list. I would like to postpone this change to #18055 however

As the method appears in this branch, I see no reason to let it be corrected in a future ticket.

Nathann

[jdemeyer]

Why is there duplication of Envelope and _upper_envelope?

[git]

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

​a0d2e63

17979: documentation for global_options

[git]

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

​3e3c7f6

Simplify Envelope by using a sign

[jdemeyer]

Replying to nthiery:

Also, at this point, we are speaking about 5-6 lines of code that are duplicated very locally.

It's more than that and it can only get worse if more features are added to Envelope.

and the code would be less straightforward.

I disagree with this. I think code duplication is always a high risk for bugs.

Anyway, I implemented this in this last commit.

[nthiery]

Replying to ncohen:

Many times in the past I had to fix code which accepts a **kwds and did not check that what it contains is actually read. This lead to silent errors or wrong output, and so I see things like global_options as the highway to bugs.

**kwds arguments can be painful, I certainly agree.

But fear not, __init__ takes no kwds. It only accepts a preexisting global_options object, and assigns it to the attribute _global_options, that's it.

Jeroen noted that this variable is actually used somewhere else, so I guess it probably should not be removed in this ticket. My comment at 319 still need to be adressed, however, as there is no documentation for this parameter. Please make it explain the uses of this flag, possibly by pointing to some other part of the doc if it is already explained somewhere else.

I had not documented it to not advertise it, since we may well get rid of it. Now there is a documentation that spells exactly what it does.

---

New commits:

​a0d2e63	17979: documentation for global_options
​3e3c7f6	Simplify Envelope by using a sign

[ncohen]

Hello,

**kwds arguments can be painful, I certainly agree.

But fear not, __init__ takes no kwds. It only accepts a preexisting global_options object, and assigns it to the attribute _global_options, that's it.

I think that my explanation above applies anyway. Unless there are checks that everything which is stored in global_options makes sense (and that there are exceptions when I do MyObject(global_options={'whatever':'whatever'} then **kwds and global_options are as dangerous as each other.

I set the ticket back to needs_work because of the previous comments on _possible_m(self, m, j, min_sum, max_sum).

Nathann

[nthiery]

Hi Jeroen,

I appreciate that you substantiate your point of view with action. I am not going to waste time debating this for I want this ticket to move forward. But I still think that the original Envelope was better, for the reasons I mentionned above. Besides, I had voluntarily used ==Infinity in my tests to not set in stone which infinity was returned.

Nicolas

[jdemeyer]

Replying to nthiery:

Besides, I had voluntarily used ==Infinity in my tests to not set in stone which infinity was returned.

I understood that, but it's cleaner this way. And if Infinity ever changes, it's a trivial change anyway.

[nthiery]

Replying to ncohen:

I think that my explanation above applies anyway. Unless there are checks that everything which is stored in global_options makes sense (and that there are exceptions when I do MyObject(global_options={'whatever':'whatever'} then **kwds and global_options are as dangerous as each other.

Whatever garbage is stored in global_options has zero influence on IntegerListsLex. If you are not happy with other classes using this feature, then change it out there. This has nothing to do with this ticket.

[jdemeyer]

Replying to ncohen:

I think that my explanation above applies anyway. Unless there are checks that everything which is stored in global_options makes sense (and that there are exceptions when I do MyObject(global_options={'whatever':'whatever'} then **kwds and global_options are as dangerous as each other.

I think this is outside the scope of this ticket.

[ncohen]

Whatever garbage is stored in global_options has zero influence on IntegerListsLex. If you are not happy with other classes using this feature, then change it out there. This has nothing to do with this ticket.

It is true. I do not think that I asked for this to be changed. I merely pointed the lack of documentation (now fixed) and explained the reason why I believe that it is a very bad practice.

Nathann

[nthiery]

Replying to jdemeyer:

Replying to nthiery:

Besides, I had voluntarily used ==Infinity in my tests to not set in stone which infinity was returned.

I understood that, but it's cleaner this way. And if Infinity ever changes, it's a trivial change anyway.

I don't see why it's cleaner; it's just a different specification. But let's move on.

[jdemeyer]

Replying to nthiery:

the computation of the area below the envelope for which we won't have this symmetry anymore.

Why not? It's just the sum of the first n values, right?

[aschilling]

Replying to jdemeyer:

Replying to nthiery:

the computation of the area below the envelope for which we won't have this symmetry anymore.

Why not? It's just the sum of the first n values, right?

The point is that this function would take backward smoothing (using the slope conditions) into account.

[jdemeyer]

Replying to aschilling:

The point is that this function would take backward smoothing (using the slope conditions) into account.

Even then, I don't see why this is incompatible with the "sign" option.

[git]

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

​eb28f87	Merge branch 'develop' into public/ticket/17979
​855685a	Merge branch 'public/ticket/17979' of git://trac.sagemath.org/sage into public/ticket/17979

[aschilling]

Replying to jdemeyer:

Replying to aschilling:

The point is that this function would take backward smoothing (using the slope conditions) into account.

Even then, I don't see why this is incompatible with the "sign" option.

You are probably right with the correct definition of the slopes.

I believe all comments have been taken into account now?

[git]

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

​58f2b55	17979: _possible_m(...) -> lookahead()
​4ff20b7	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

[nthiery]

Replying to ncohen:

I set the ticket back to needs_work because of the previous comments on _possible_m(self, m, j, min_sum, max_sum).

Done.

[nthiery]

Replying to jdemeyer:

Replying to nthiery:

the computation of the area below the envelope for which we won't have this symmetry anymore.

Why not? It's just the sum of the first n values, right?

Mathematically, and up to smoothing, yes. The algorithmic will be somewhat more involved than this for achieving good complexity, but fair enough, I guess it can be made to work.

[git]

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

​03f007c

17979: improved doc of lower/upper_envelope

[nthiery]

Replying to jdemeyer:

Why is there duplication of Envelope and _upper_envelope?

The role of _upper_envelope is to slightly tweak the global ceiling (an existing already smoothed Envelope object) to take into account the additional local constraint that the current value at position j is m. Similarly for _lower_envelope.

So the two features are similar in the nature of their goal, but differ in what they actually need to do to achieve it. So merging them is unlikely to save any duplication while likely to add complexity.

On the other hand, I agree it would be nice to better clarify this distinction between the two features in the method names. Suggestions welcome.

---

New commits:

​03f007c

17979: improved doc of lower/upper_envelope

[jdemeyer]

Since _upper_envelope deals with ceiling bounds and refers only to information which is already contained in _ceiling, it looks like _upper_envelope should really be a method of Envelope (then better without the leading underscore). So please justify why you think this should not be the case.

[git]

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

​2c7019c

17979: _upper_bound / _lower_bound -> adapt method of Envelope

[nthiery]

Replying to jdemeyer:

Since _upper_envelope deals with ceiling bounds and refers only to information which is already contained in _ceiling, it looks like _upper_envelope should really be a method of Envelope (then better without the leading underscore). So please justify why you think this should not be the case.

I agree that it's better; thanks for the suggestion! Done.

Cheers,

Nicolas

[nthiery]

We have been working hard to make the deadline for the release. Like in any piece of code, there certainly are other internal micro-refactoring that could possibly be done. If you note one, please be specific on whether you believe it really needs to be done now, or could be postponed to one of the follow up tickets; especially since some of those tickets may well induce complete rewrite of the ditto micro-refactored code anyway.

[ncohen]

We have been working hard to make the deadline for the release. Like in any piece of code, there certainly are other internal micro-refactoring that could possibly be done. If you note one, please be specific on whether you believe it really needs to be done now, or could be postponed to one of the follow up tickets; especially since some of those tickets may well induce complete rewrite of the ditto micro-refactored code anyway.

Have you had the impression that some of our previous requests were abusive? We try to understand your code, make sure that it is correct maintenable and thus that it will be easy to understand and work on it in the future.

Many of the things that seem obvious to the author are not easily deduced when you only look at the code, and unexpected design choices often raise more questions.

I personally gave up raising some arguments (that still seem legitimate to me) only to lessen the load on this ticket. I still plan to read the code you implement totally (I haven't done that yet), and I will probably have more time to do so next week.

Nathann

[jdemeyer]

One more "adding constraints break" issue:

sage: IntegerListsLex(5, max_part=0).list()
[]
sage: IntegerListsLex(5, max_part=0, min_slope=0).list()
...
ValueError: Could not check that the specified constraints yield a finite set

[jdemeyer]

This is a more difficult example where the list is finite (because the sum of the lower envelope eventually becomes larger than the sum):

sage: IntegerListsLex(7, floor=[4], max_part=4, min_slope=-1).list()
...
ValueError: Could not check that the specified constraints yield a finite set

This should either be fixed or be documented as an example where the check isn't good enough.

[jdemeyer]

I do find it surprisingly inconsistent that

sage: IntegerListsLex(7, floor=[4,3,2,1], max_part=4, min_slope=-1).list()

works but

sage: IntegerListsLex(7, floor=[4], max_part=4, min_slope=-1).list()

does not.

[jdemeyer]

This hangs:

sage: IntegerListsLex(7, max_part=0, ceiling=lambda i:i).list()

[jdemeyer]

In _check_finiteness(), I think you should move from a blacklist model to a whitelist model: don't raise an exception if certain conditions are satisfied, but raise an error unless the input can be seen to be finite. This logic could not have the problem that adding conditions breaks things.

[nthiery]

Replying to ncohen:

Have you had the impression that some of our previous requests were abusive? We try to understand your code, make sure that it is correct maintenable and thus that it will be easy to understand and work on it in the future.

Many of the things that seem obvious to the author are not easily deduced when you only look at the code, and unexpected design choices often raise more questions.

Abusive, no: they all had to be handled at some point or the other. Urgent: I did wonder for some of them; I agree that we absolutely want the code to be correct (at least to the best of our knowledge) for this rc. And this of course requires a complete understanding of it by the reviewers, and clarification of the design choices. But maybe for some of the issues it's sufficient, once things are clarified, to leave a note in upcoming tickets for the next step that need to be done.

The big thing is that I have the impression to be holding off the upcoming rc, and that's rather uncomfortable. Also having a stable base here would allow me to move on to the following tasks, in particular working of the merge and review of #17920, as well as your ticket about IntegerVectors?. And also would allow me or others to work on to the follow up tickets.

I personally gave up raising some arguments (that still seem legitimate to me) only to lessen the load on this ticket.

I appreciate this! Please add these comments to the followup tickets (or some new one if appropriate), for I want to hear about them.

I still plan to read the code you implement totally (I haven't done that yet), and I will probably have more time to do so next week.

Great, thanks!

From the many discussions with you, Jeroen, Bryan, and Anne and myself, it seems that the code has been scrutinized quite some. As Jeroen pointed out, there are still cases that could be handled in theory, and that the code rejects at this point. But outside of those situations, I pretty much trust that the code gives correct result. Which achieves the original goal of this ticket.

Cheers,

Nicolas

[git]

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

​7a35dc6

17979: rewrite _check_finiteness using a whitelist of proven good cases

[nthiery]

Replying to jdemeyer:

In _check_finiteness(), I think you should move from a blacklist model to a whitelist model: don't raise an exception if certain conditions are satisfied, but raise an error unless the input can be seen to be finite. This logic could not have the problem that adding conditions breaks things.

Agreed. It's also easier to check step by step the correctness of each good case. Done.

I am pretty sure I got the list of good cases right. But it's 1 am, so please double check that I did not inadvertently remove a good case. At least all tests in this file pass, and 386 is now fixed.

---

New commits:

​7a35dc6

17979: rewrite _check_finiteness using a whitelist of proven good cases

[git]

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

​3fab366

17979: document the existence of false negatives for _check_finiteness, illustrated with Jeroen's example

[nthiery]

Replying to jdemeyer:

I do find it surprisingly inconsistent that

sage: IntegerListsLex(7, floor=[4,3,2,1], max_part=4, min_slope=-1).list()

works but

sage: IntegerListsLex(7, floor=[4], max_part=4, min_slope=-1).list()

does not.

Annoying indeed. The fine point is in the heuristic to decide how deep we want to lookahead to find a lower bound on the total floor area. In a case like this we could potentially compute how deep to go until the floor would reach its limit of zero.

I would tend to postpone that: there is no risk of wrong answer, the existence of false negatives is now documented in _check_finiteness (using the above examples), and the user can set check=False to workaround the limitation.

What do you think?

[git]

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

​11afea3

17979: we *want* to run the finiteness checks even if the input are functions + added related documentation

[git]

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

​3ae7f09

17979: removed useless lines detected by pyflakes

[git]

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

​f5e9eef

17979: fixed hang reported in comment:389

[git]

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

​43a55e3

17979: non negative -> nonnegative

[nthiery]

Time to call it a day.

Back to needs review (assuming for now that comment:395 is ok).

[git]

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

​e151d78

17979 trivial doc fixes

[aschilling]

Regarding Jeroen's comment:395, I think this could possibly be fixed by adjusting ._floor.limit_start() after the smoothing procedure. Note that

sage: C=IntegerListsLex(7, floor=[4,0], max_part=4, min_slope=-1)
sage: C.list()
[[4, 3]]

also works fine. The reason is that

sage: C._floor.limit_start()
2

so that

floor_sum_lower_bound = sum(self._floor(i) for i in range(self._floor.limit_start()))

in line 1076 computes a high enough bound that is caught in line 1082. However, in

sage: C=IntegerListsLex(7, floor=[4], max_part=4, min_slope=-1)
sage: C._floor.limit_start()
1

even though

sage: for i in range(5):
....:     print C._floor(i)
....:     
4
3
2
1
0

[jdemeyer]

Replying to nthiery:

I pretty much trust that the code gives correct result.

To be clear: during all my testing I didn't find a single example where the code actually returned a wrong result. On the other hand, there were many hangs or cases where a superfluous ValueError was raised.

[nthiery]

Replying to jdemeyer:

Replying to nthiery:

I pretty much trust that the code gives correct result.

To be clear: during all my testing I didn't find a single example where the code actually returned a wrong result. On the other hand, there were many hangs or cases where a superfluous ValueError was raised.

This indeed was my overall impression of your comments. Thanks for confirming!

[nthiery]

Replying to aschilling:

Regarding Jeroen's comment:395, I think this could possibly be fixed by adjusting ._floor.limit_start() after the smoothing procedure.

Agreed: we could imagine, in the constructor of Envelope and when a list is given as input, to set limit_start not to the end of the list, but to the point where the limit is actually reached after smoothing. It should be just a couple lines.

Potential downside: if the parts in the list are very high, this may induce a similarly high limit start, which will trigger more calculations elsewhere. Probably not a common use case, so we might not care.

The other thing is that I could well imagine that, once the new lookahead is implemented in #18055, the finiteness checking -- or at least the partial lookahead we are doing in _check_finiteness -- would become a side product; so might not be worth having something temporary.

So, reviewers: let us know if this should be done right now.

Cheers,

Nicolas

[vbraun]

In the interest of ever releasing sage-6.6 I would prefer to finish a version that provides correct answers now and optimize it later...

[jdemeyer]

I personally have no further comments regarding this ticket. I have tested it a lot in practice, trying hard to break it. I have read most of the structural code, but not the actual algorithm. I would agree with a positive_review for this ticket except for the changes to integer_vector.py.

[ncohen]

Replying to jdemeyer:

I personally have no further comments regarding this ticket. I have tested it a lot in practice, trying hard to break it. I have read most of the structural code, but not the actual algorithm.

I will do a full review today or tomorrow. Most probably all changes have already been made.

Nathann

[nthiery]

Replying to jdemeyer:

I personally have no further comments regarding this ticket. I have tested it a lot in practice, trying hard to break it.

To say the least!

I have read most of the structural code, but not the actual algorithm. I would agree with a positive_review for this ticket

Thanks for the hard work :-)

except for the changes to integer_vector.py.

Yup. Note for the release manager: those were checked and validated by Travis and Anne.

[jdemeyer]

Replying to nthiery:

Yup. Note for the release manager: those were checked and validated by Travis and Anne.

I prefer to hear this from them instead of you speaking for them.

[nthiery]

Replying to jdemeyer:

Replying to nthiery:

Yup. Note for the release manager: those were checked and validated by Travis and Anne.

I prefer to hear this from them instead of you speaking for them.

Sure thing. Anne? Travis?

(see also 248, 254)

[ncohen]

Hello,

This is what I did during the last 3~4 hours. I stopped before the end and did not review m_interval, _lookahead nor the code of Envelope, as I really should be working on mathematics instead of Sage T_T

Some are easy, some are harder. Also, let me write somewhere that I am against keeping integer_list_old in Sage, as I am afraid that it will still be here several years from now. Here are my comments:

• Module documentation -- in the 'itemize' section listing IntegerListsLex and Envelope, could you add a short description of what they are meant for?

• Why a 'history' section?

• Documentation of IntegerListsLex: instead of stating the *purpose* of the class (which is more something one would explain on a trac ticket), what about a SEEALSO section? I have the following paragraph in mind:

  The main purpose is to provide a generic iteration engine for all
  the enumerated sets like :class:`Partitions`,
  class:`Compositions`, :class:`IntegerVectors`. It can also be
  used to generate many other combinatorial objects like Dyck paths,
  Motzkin paths, etc.
  

  I thought that it would make more sense as a SEEALSO section pointing toward the mentionned objects.

• About this paragraph:

  The set of allowable constraints has been specifically designed to enable
  iteration with a good time and memory complexity in most practical use cases,
  and in inverse lexicographic order (see below)
  

I do not believe that it is true, i.e. that the set of allowable contraints has been specifically designed to enable iteration with a good time and memory complexity.

In particular, it is possible to get great speed improvements by writing a Constant Amortized Algorithm to list only partitions satisfying a smaller set of constraints like (sum,length,min/max part).

This statement sounds wrong to me, and so I believe that it should be removed.

• Documentation of the parameter n -- you say that a list of integers can be provided but do not explain what the output will be.

• Are min_sum and max_sum also ignored when n is a list? From the doc it seems to be, though I am not sure that it is the best design choice in this case.

• I was surprised by the following output:

  sage: IntegerListsLex(3,max_length=3,floor=[1,1,1]).list()
  [[3], [2, 1], [1, 2], [1, 1, 1]]
  

  I woud have expected the length of the lists to be at least 3, as I requested the first three parts to be >=1. The documentation is consistent, but I still find it surprising.

• check seems misnamed. It is not about checking the input or output, only about displaying warnings. What about disable_warnings instead?

• In the following text which says that one can force the enumeration when it is formally impossible, can you explicitly say what will happen? "All possible lists are enumerated, but the ordering is incorrect" or something? If one wants to proceed anyway, one can sign a waiver by setting check=False:

• About the finiteness check: what about a specific allow_infinite_iterator independent from the current 'check'.

• Building the doc of integer_list.py with --warn-links fails.

• sage: list(IntegerListsLex(3, max_length=2, ))

• Lexicographic ordering is broken when n is a list.

  sage: print IntegerListsLex([1,2],length=3).list()
  [[1, 0, 0], [0, 1, 0], [0, 0, 1], [2, 0, 0], [1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1], [0, 0, 2]]
  

In particular, the output differs depending on how n is sorted.

• Cardinality is broken when n is a list

  sage: IntegerListsLex(3,length=3).cardinality()
  10
  sage: IntegerListsLex([3,3],length=3).cardinality()
  20
  

• return typecall(cls, n=n, **kwargs) -- for clarity I find the normal syntax better. This place is not a critical part for speed, especially when you create DisjointUnionEnumeratedSets with lambda functions just above.

• I had not noticed that IntegerListsLex objects could have a 'name' argument.. As all arguments, it must be documented in the INPUT section.

• Same for element_constructor and element_class.

• self._max_length = ZZ(max_length) if max_length != Infinity else max_length Just my two cents: I would return 'Infinity' instead of max_length. You defined your Infinity in order to be fast, and you don't know what max_length may be. This occurs several times.

• You can save space and turn the two following tests into one (using the same 'all'). Occurs twice.

  if not all(i in ZZ for i in floor):
      raise TypeError("the parts of floor={} should be nonnegative integers".format(floor))
  if not all(i >= 0 for i in floor):
      raise NotImplementedError("negative parts in floor={}".format(floor))
  

  This would also solve the following, which tests ceiling but mentions floor

  if not all(i >= 0 for i in ceiling):
      raise NotImplementedError("negative parts in floor={}".format(ceiling))
  

• # constructor is known to be safe and don't claim ownership on -- "does not".

• Typing IntegerListsLex.<tab> in the console is very entertaining. I would be very glad if we some day decide to consider this as a bug.

• about check_finiteness -> what about guess_finiteness instead, to emphasize that the function makes mistakes?

• The error message when the set is infinite is misleading:

  sage: L = IntegerListsLex(4)
  sage: L._check_finiteness()
  ...
  ValueError: Could not check that the specified constraints yield a finite set
  

  The code was able to perform the check, though it was not "able to decide that the set is finite".

• I do not understand this comment: If a part has no bound on its value, it will be detected at some point Do you mean that "at some point in iter" it will be detected? Probably not, as this function is called only once.

• The function _check_finiteness assumes that the alphabet size is bounded. It is always true when this function is called, but the following raises no warning:

  sage: for x in IntegerListsLex(NonNegativeIntegers(),max_length=3):
  ....:     pass
  

  For the reason given earlier, the output is not sorted lexicographically. It is not detected as infinite either.

• The many if A: return from _check_finiteness can be replaced by a `if A or B or C or ...: return`.

• in _check_finiteness: the documentation of limit() says that it is only an upper bound. Thus you cannot write the following:

  if self._ceiling.limit() < self._floor.limit():
      return
  

• Same comment here

  if self._floor.limit() > 0 or self._min_slope > 0:
     floor_sum_lower_bound = Infinity
  

• Also, it seems that limit_start() can be Infinity, in which case one cannot deduce anything from the value of limit. Please add checks.

• I stop reviewing _check_finiteness, as it is complicated while the situation of limit() is not cleared.

• Which specific bound is returned is not set in stone. Be more accurate.

Nathann

[jdemeyer]

Replying to ncohen:

• About this paragraph:

  The set of allowable constraints has been specifically designed to enable
  iteration with a good time and memory complexity in most practical use cases,
  and in inverse lexicographic order (see below)
  

...

This statement sounds wrong to me, and so I believe that it should be removed.

Agreed.

• I was surprised by the following output:

  sage: IntegerListsLex(3,max_length=3,floor=[1,1,1]).list()
  [[3], [2, 1], [1, 2], [1, 1, 1]]
  

  I woud have expected the length of the lists to be at least 3, as I requested the first three parts to be >=1. The documentation is consistent, but I still find it surprising.

What should be done to make it less surprising? It is completely consistent with min_part=1.

• check seems misnamed. It is not about checking the input or output, only about displaying warnings. What about disable_warnings instead?

I asked for this argument to be called check. Usually, it's exceptions which are controlled by a check argument, but I don't see why this cannot be warnings instead.

• self._max_length = ZZ(max_length) if max_length != Infinity else max_length Just my two cents: I would return 'Infinity' instead of max_length. You defined your Infinity in order to be fast, and you don't know what max_length may be. This occurs several times.

Agreed, see also integer_or_infinity from #17920.

• I do not understand this comment: If a part has no bound on its value, it will be detected at some point Do you mean that "at some point in iter" it will be detected? Probably not, as this function is called only once.

Agreed that this is confusing. This comment should really be moved to and explained the docstring.

• The many if A: return from _check_finiteness can be replaced by a `if A or B or C or ...: return`.

That's just a matter of style. The many if A: return might be more clear to read...

[tscrim]

I'm okay with the state of integer_vector.py.

[nthiery]

Thanks Nathann for the comments. I'll work on them tomorrow in the plane, taking off at 1pm here. In case you'd have a chance to throw some more before then, I could investigate them at the same occasion.

Cheers,

Nicolas

[git]

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

​887d2b8

17979: more details in the module description + tiny doc improvement in Envelope

[git]

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

​8c6d433

17979: convert all input to use our Infinity in __init__

[nthiery]

Hi,

I'll answer in several chunks, since I am not sure if I can take care of all before taking off.

Replying to ncohen:

• Module documentation -- in the 'itemize' section listing IntegerListsLex and Envelope, could you add a short description of what they are meant for?

Done. This is quite redundant, so I was not sure what to put. Feel free to edit to your taste.

• Why a 'history' section?

Quite often the history is unnecessary because all the information is in the git history. But here the history spans other software and is harder to follow since the previous file was moved. This also gives credit/blame record, and some sort of bibliography since there is no published description of the algorithm (at least not yet).

• self._max_length = ZZ(max_length) if max_length != Infinity else max_length Just my two cents: I would return 'Infinity' instead of max_length. You defined your Infinity in order to be fast, and you don't know what max_length may be. This occurs several times.

Good point; I had hesitated but this is better. Fixed.

• You can save space and turn the two following tests into one (using the same 'all'). Occurs twice.

  if not all(i in ZZ for i in floor):
      raise TypeError("the parts of floor={} should be nonnegative integers".format(floor))
  if not all(i >= 0 for i in floor):
      raise NotImplementedError("negative parts in floor={}".format(floor))
  

  This would also solve the following, which tests ceiling but mentions floor

  if not all(i >= 0 for i in ceiling):
      raise NotImplementedError("negative parts in floor={}".format(ceiling))
  

Jeroen asked for a different error message (TypeError w.r.t. NotImplementedError), and I agree with him; so I did not change this. But I fixed the floor to ceiling in the error message. Note btw that the TypeError is now done through a conversion to a tuple of ZZ.

---

New commits:

​887d2b8	17979: more details in the module description + tiny doc improvement in Envelope
​8c6d433	17979: convert all input to use our Infinity in __init__

[nthiery]

Replying to ncohen: Also, let me write somewhere that I

am against keeping integer_list_old in Sage, as I am afraid that it will still be here several years from now.

We definitely should keep it around for benchmarking purposes at least until #18055 is finished. I am fine adding the removal of integer_list_old to the todo list for this ticket.

• Documentation of IntegerListsLex: instead of stating the *purpose* of the class (which is more something one would explain on a trac ticket), what about a SEEALSO section? I have the following paragraph in mind:

  The main purpose is to provide a generic iteration engine for all
  the enumerated sets like :class:`Partitions`,
  class:`Compositions`, :class:`IntegerVectors`. It can also be
  used to generate many other combinatorial objects like Dyck paths,
  Motzkin paths, etc.
  

  I thought that it would make more sense as a SEEALSO section pointing toward the mentionned objects.

A user reading this documentation is likely to know about integer partitions, compositions or such. Mentioning them early on gives immediately an idea of the range of applications, and thus a better understanding of the upcoming description of the specific input. So I would want this text to come before the long description of the input. I am fine making it into a SEEALSO if that's ok to put one before INPUT.

Also it's also a useful piece of information for users, even more for developers, to better understand the architecture, and know when to use this class or another one. Such information really belongs to the documentation, not trac.

[git]

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

​ea044ad

17979: fixed cross links + typo in error message

[git]

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

​ac68bde

17979: documentation for

[ncohen]

We definitely should keep it around for benchmarking purposes at least until #18055 is finished. I am fine adding the removal of integer_list_old to the todo list for this ticket.

I do not see the point. You can checkout Sage 6.5 whenever you like if you ever need to benchmark this old (and broken) code.

A user reading this documentation is likely to know about integer partitions, compositions or such.

You cannot make assumptions like that. A user might find this class because he was redirected there after reading the doc of IntegerVectors (for instance).

I am fine making it into a SEEALSO if that's ok to put one before INPUT.

Works for me.

Nathann

[nthiery]

Replying to ncohen:

• Documentation of the parameter n -- you say that a list of integers can be provided but do not explain what the output will be.
• Building the doc of integer_list.py with --warn-links fails.

Fixed.

[jdemeyer]

I would prefer not to have integer_list_old in the reference manual. It's deprecated, you're not supposed to use it. So let's at least pretend that it doesn't exist.

[git]

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

​84489c6

17979 removed integer_list_old from reference manual

[aschilling]

Replying to jdemeyer:

I would prefer not to have integer_list_old in the reference manual. It's deprecated, you're not supposed to use it. So let's at least pretend that it doesn't exist.

I agree with this. Fixed!

[git]

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

​8843650

17979 explained list with repeated entries

[aschilling]

• Are min_sum and max_sum also ignored when n is a list? From the doc it seems to be, though I am not sure that it is the best design choice in this case.

Yes. As far as I know this is how it was before.

• I was surprised by the following output:

  sage: IntegerListsLex(3,max_length=3,floor=[1,1,1]).list()
  [[3], [2, 1], [1, 2], [1, 1, 1]]
  

  I woud have expected the length of the lists to be at least 3, as I requested the first three parts to be >=1. The documentation is consistent, but I still find it surprising.

As Jeroen mentioned, floor just requires that if there is a part, then it satisfies the constraint. If no part is present, that is ok. If you want at least three parts, you need to specify min_length.

• check seems misnamed. It is not about checking the input or output, only about displaying warnings. What about disable_warnings instead?

Jeroen had asked us to change this. So please first agree among yourself before asking to change this again.

• In the following text which says that one can force the enumeration when it is formally impossible, can you explicitly say what will happen? "All possible lists are enumerated, but the ordering is incorrect" or something? If one wants to proceed anyway, one can sign a waiver by setting check=False:

When a function for the floor or ceiling is given, it is impossible to check that the conditions give a finite set since the list of values is in principle infinite. In this case the algorithm can either hang (as it computes more and more parts of the integer list) or it can happen that a tail of 000100000.... will appear in which case nor all elements in the list will be iterated over.

• sage: list(IntegerListsLex(3, max_length=2, ))

Fixed.

• Lexicographic ordering is broken when n is a list.

  sage: print IntegerListsLex([1,2],length=3).list()
  [[1, 0, 0], [0, 1, 0], [0, 0, 1], [2, 0, 0], [1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1], [0, 0, 2]]
  

In particular, the output differs depending on how n is sorted.

• Cardinality is broken when n is a list

  sage: IntegerListsLex(3,length=3).cardinality()
  10
  sage: IntegerListsLex([3,3],length=3).cardinality()
  20
  

See the documentation!

[ncohen]

• Are min_sum and max_sum also ignored when n is a list? From the doc it seems to be, though I am not sure that it is the best design choice in this case.

Yes. As far as I know this is how it was before.

What do you think of it?

• In the following text which says that one can force the enumeration when it is formally impossible, can you explicitly say what will happen? "All possible lists are enumerated, but the ordering is incorrect" or something? If one wants to proceed anyway, one can sign a waiver by setting check=False:

When a function for the floor or ceiling is given, it is impossible to check that the conditions give a finite set since the list of values is in principle infinite. In this case the algorithm can either hang (as it computes more and more parts of the integer list) or it can happen that a tail of 000100000.... will appear in which case nor all elements in the list will be iterated over.

Can you make this explicit in the doc?

See the documentation!

It does not address the problem that output is not sorted as it should.

Nathann

[git]

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

​0a31f21	17979: fixed typo
​293e6fb	17979: more documentation and caveat about n=[...]
​1b8ce07	17979: more documentation and caveat about n=[...] ...
​7fdaf5d	17979: typo fix
​66643f0	17979: documentation for name, element_class, element_constructor + use Parent's element_constructor option
​570d61d	17979: improved documentation and error reporting in _check_finiteness
​0774e3f	17979: documentation and tests for the limit bound for lower envelopes
​de23fcf	17919: more precise specification of Envelope.limit
​d6ead16	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

[aschilling]

Replying to ncohen:

• Are min_sum and max_sum also ignored when n is a list? From the doc it

seems to be, though I am not sure that it is the best design choice in this case.

Yes. As far as I know this is how it was before.

What do you think of it?

As stated in the documentation, this feature is kept for backward compatibility, see

sage: from sage.combinat.integer_list_old import IntegerListsLex as IntegerListsLexOld
sage: IntegerListsLexOld([2,2],length=2).list()
/Applications/sage/src/bin/sage-ipython:1:
********************************************************************************
The old implementation of IntegerListsLex does not allow for arbitrary input; non-allowed input can return wrong results, please see the documentation for IntegerListsLex for details.
This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/17548.
********************************************************************************
[[2, 0], [1, 1], [0, 2], [2, 0], [1, 1], [0, 2]]

• In the following text which says that one can force the enumeration when it is

formally impossible, can you explicitly say what will happen? "All possible lists are enumerated, but the ordering is incorrect" or something? If one wants to proceed anyway, one can sign a waiver by setting check=False:

When a function for the floor or ceiling is given, it is impossible to check that the conditions give a finite set since the list of values is in principle infinite. In this case the algorithm can either hang (as it computes more and more parts of the integer list) or it can happen that a tail of 000100000.... will appear in which case nor all elements in the list will be iterated over.

Can you make this explicit in the doc?

It is. See line 403 onward.

See the documentation!

It does not address the problem that output is not sorted as it should.

It is documented what it does and that it does not sort it the way you suggest. See line 496 onward.

[git]

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

​92bc243

17979 fixed doubled up doc test

[aschilling]

The following is weird behavior that needs to be fixed!!

sage: IntegerListsLex([2,2],length=2).list()
[[2, 0], [1, 1], [0, 2], [2, 0], [1, 1], [0, 2]]
sage: IntegerListsLex([2,2],length=3).list()
[[2, 0], [1, 1], [0, 2], [2, 0], [1, 1], [0, 2]]

The answer should really be

sage: IntegerListsLex([2,2],length=3).list()
[[2, 0, 0],
 [1, 1, 0],
 [1, 0, 1],
 [0, 2, 0],
 [0, 1, 1],
 [0, 0, 2],
 [2, 0, 0],
 [1, 1, 0],
 [1, 0, 1],
 [0, 2, 0],
 [0, 1, 1],
 [0, 0, 2]]

---

New commits:

​92bc243

17979 fixed doubled up doc test

[aschilling]

Replying to ncohen:

• I do not understand this comment: If a part has no bound on its value, it will be detected at some point Do you mean that "at some point in iter" it will be detected? Probably not, as this function is called only once.

It will be detected during the algorithm that builds up the integer vector successively. The algorithm tries to add each part and if at some point the bound on a part is infinite, then it will raise an error.

• The function _check_finiteness assumes that the alphabet size is bounded. It is always true when this function is called, but the following raises no warning:

  sage: for x in IntegerListsLex(NonNegativeIntegers(),max_length=3):
  ....:     pass
  

  For the reason given earlier, the output is not sorted lexicographically. It is not detected as infinite either.

_check_finiteness only tests this for each piece in the DisjointEnumeratedSet? (when a list is given for n) and checks that each piece is a finite set.

[git]

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

​2380fd4

17979: safe if not perfect implementation of equality tests

[nthiery]

Replying to aschilling:

The following is weird behavior that needs to be fixed!!

sage: IntegerListsLex([2,2],length=2).list()
[[2, 0], [1, 1], [0, 2], [2, 0], [1, 1], [0, 2]]
sage: IntegerListsLex([2,2],length=3).list()
[[2, 0], [1, 1], [0, 2], [2, 0], [1, 1], [0, 2]]

The answer should really be

sage: IntegerListsLex([2,2],length=3).list()
[[2, 0, 0],
 [1, 1, 0],
 [1, 0, 1],
 [0, 2, 0],
 [0, 1, 1],
 [0, 0, 2],
 [2, 0, 0],
 [1, 1, 0],
 [1, 0, 1],
 [0, 2, 0],
 [0, 1, 1],
 [0, 0, 2]]

Fixed!

[nthiery]

On Tue, Apr 07, 2015 at 03:06:42PM -0000, sage-trac wrote:

• Lexicographic ordering is broken when n is a list.

     sage: print IntegerListsLex([1,2],length=3).list()
     [[1, 0, 0], [0, 1, 0], [0, 0, 1], [2, 0, 0], [1, 1, 0], [1, 0, 1], [0,
   2, 0], [0, 1, 1], [0, 0, 2]]
  

In particular, the output differs depending on how n is sorted.

Indeed, and this is in fact a feature. I reworked the documentation to better highlight this.

• Cardinality is broken when n is a list

  sage: IntegerListsLex(3,length=3).cardinality()
  10
  sage: IntegerListsLex([3,3],length=3).cardinality()
  20
  

I documented this behavior some more. That's part of the specifications that this returns a disjoint union. A different specification might look desirable, but there would be no efficient way to handle it.

• return typecall(cls, n=n, **kwargs) -- for clarity I find the normal syntax better. This place is not a critical part for speed, especially when you create DisjointUnionEnumeratedSets with lambda functions just above.

I am not sure what you mean by "normal syntax". That you prefer using DisjointUnionEnumeratedSets? directly rather than this syntactic sugar?

• Are min_sum and max_sum also ignored when n is a list? From the doc it seems to be, though I am not sure that it is the best design choice in this case.

Indeed they are ignored. I don't see a simple way to implement it otherwise.

Speaking of which: should there be a warning when a user-specified value for min_sum or max_sum is overridden by n? Same for length versus min_length and max_length.

• I was surprised by the following output:

  sage: IntegerListsLex(3,max_length=3,floor=[1,1,1]).list()
  [[3], [2, 1], [1, 2], [1, 1, 1]]
  

I would have expected the length of the lists to be at least 3, as I requested the first three parts to be >=1. The documentation is consistent, but I still find it surprising.

I agree it can be surprising at first sight, but the other way round would have prevented interesting use cases. Not that some of the specialized classes, like partitions or integer vectors, take a separate argument inner and outer which does impose length restrictions, according to the usual math vocable in those contexts.

• check seems misnamed
• About the finiteness check: what about a specific allow_infinite_iterator independent from the current 'check'.

I also wondered, but see the discussion with Jeroen: let's keep things simple until we actually meet a serious use case.

• {{{# constructor is known to be safe and don't claim ownership

on}}} -- "does not".

Done.

• Typing IntegerListsLex.<tab> in the console is very entertaining. I would be very glad if we some day decide to consider this as a bug.

Agreed: about one half of the items should not be there. But that's a different discussion.

• I had not noticed that IntegerListsLex objects could have a 'name' argument.. As all arguments, it must be documented in the INPUT section.
• Same for element_constructor and element_class.

Done.

• The error message when the set is infinite is misleading:

     sage: L = IntegerListsLex(4)
     sage: L._check_finiteness()
     ...
     ValueError: Could not check that the specified constraints yield a
   finite set
  

  The code was able to perform the check, though it was not "able to decide that the set is finite".

Good point. At the end of the day, I made it into "could not prove that the set is finite" which better highlights the lack of symmetry.

• I do not understand this comment: {{{If a part has no bound on its value, it will be detected at some point}}} Do you mean that "at some point in iter" it will be detected? Probably not, as this function is called only once.

I rewrote the documentation of _check_finiteness to be more specific and discuss this point.

• about check_finiteness -> what about guess_finiteness instead, to emphasize that the function makes mistakes?

I see your point; however guess improperly suggests that it's going to return a boolean, whereas check conveys that it's about trying to catch and report bad situations.

Another issue with this name, which is even more apparent with the rewrite of the documentation, is that this method is really about trying to prove the existence of a bound on the length.

Oh well, I believe it's good enough for now; it's a private method with an extensive documentation giving a precise specification; if someone comes up with a perfect name, it's a trivial change. Besides check conveys that the verification needs not be comprehensive.

• The function _check_finiteness assumes that the alphabet size is bounded. It is always true when this function is called, but the following raises no warning:

  sage: for x in IntegerListsLex(NonNegativeIntegers(),max_length=3):
  ....:     pass
  

  For the reason given earlier, the output is not sorted lexicographically. It is not detected as infinite either.

Correct, which is fine: the above example is properly iterable, and it's nowhere claimed to be finite:

sage: C = IntegerListsLex(NonNegativeIntegers(),max_length=3)
sage: C in EnumeratedSets().Finite()
False

In general, it's documented that n=iterable is nothing but a convenience, and that it does not return an IntegerListsLex object but a disjoint union thereof. I would not want to pollute the documentation everywhere with straightforward consequences.

• The many if A: return from _check_finiteness can be replaced by a `if A or B or C or ...: return`.

As Jeroen says, that's a matter of style. Here I like that it highlights the fact that each test is independent. So the reader can think about just one at a time.

• in _check_finiteness: the documentation of limit() says that it is only an upper bound. Thus you cannot write the following:

  if self._ceiling.limit() < self._floor.limit():
      return
  

• Same comment here

  if self._floor.limit() > 0 or self._min_slope > 0:
     floor_sum_lower_bound = Infinity
  

Jeroen's fault! (Just kidding :-) )

That's actually correct: for the floor, limit in fact returns a lower bound. I reinstated the documentation and tests for this as they had gotten scrambled in the sign-refactoring of Envelope.

• Also, it seems that limit_start() can be Infinity, in which case one cannot deduce anything from the value of limit. Please add checks.

Ah yes, the specifications of limit / limit_start were not explicit in this case. Fixed. With those specs, the deduction is actually correct.

• I stop reviewing _check_finiteness, as it is complicated while the situation of limit() is not cleared.

Hopefully it's cleared now!

• Which specific bound is returned is not set in stone. Be more accurate.

I tried to make the sentence clearer.

More tomorrow. Off to bed now!

Cheers from Montreal,

Nicolas

[git]

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

​0bff449

17979: minor improvement to the doc of limit_start

[ncohen]

Hello Nicolas,

I reported the following problems:

• From the doumentation: infinite set, no warning:

  sage: for x in IntegerListsLex(NonNegativeIntegers(),length=1):
  ....:     pass
  

• Non ordered output:

  sage: IntegerListsLex([1,2],length=3).list()
  [[1, 0, 0],
   [0, 1, 0],
   [0, 0, 1],
   [2, 0, 0],
   [1, 1, 0],
   [1, 0, 1],
   [0, 2, 0],
   [0, 1, 1],
   [0, 0, 2]]
  

Indeed, and this is in fact a feature. I reworked the documentation to better highlight this.

I consider this example to break what the class promises (by being called IntegerListsLex): its output is not sorted lexicograpically.

Now, I agree that this is hard to fix inside of the class. Thus instead of claiming that it is not a bug by adding a line of documentation (which is why you are rewriting the class today) please consider deprecating it. Updating the code that calls it should not be a problem, as it can call DisjointUnionEnumeratedSets directly.

Nathann

[jdemeyer]

Replying to ncohen:

Now, I agree that this is hard to fix inside of the class. Thus instead of claiming that it is not a bug by adding a line of documentation (which is why you are rewriting the class today) please consider deprecating it.

I completely agree with you in principle. However, I would be against adding even more changes to other parts of Sage.

As far as I can tell, within the Sage library, IntegerListsLex is only called in the following ways:

1. with n a single number -> this is good
2. with range(a,b) -> this can easily be changed to use min_sum and max_sum
3. with NN -> keep this for now

For now, I agree with deprecating lists or iterables. I would keep support for NN and deal with that on a follow-up ticket.

[ncohen]

I completely agree with you in principle. However, I would be against adding even more changes to other parts of Sage.

Then a stopgap can be added (in this ticket) when IntegerListsLex is created from something which is not an integer. It does not change any of the doctests.

Nathann

[jdemeyer]

Nathann, I'll have a look. Perhaps the changes are not so dramatic as I thought.

[git]

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

​3363aeb

Deprecate IntegerListsLex(n) where n is an iterable

[jdemeyer]

Nathann, is this OK for you?

[ncohen]

Nathann, is this OK for you?

I would have changed the calls to make them use DisjointUnionEnumeratedSet directly, but if you think that this deserves a function then no proble.

I noticed something wrong in the words file, and created ticket #18148 to address it.

Nathann

[nthiery]

Replying to ncohen:

We definitely should keep it around for benchmarking purposes at least until #18055 is finished. I am fine adding the removal of integer_list_old to the todo list for this ticket.

I do not see the point. You can checkout Sage 6.5 whenever you like if you ever need to benchmark this old (and broken) code.

Yes, and wait for the recompilation. Or keep yet another copy of Sage around just for this. It also makes it more complicated to compare outputs. Really, there is no risks associated to keeping it around for a bit more time, and *not* keeping it is just another useless hurdle in the way of those who will be working on #18055.

A user reading this documentation is likely to know about integer partitions, compositions or such.

You cannot make assumptions like that. A user might find this class because he was redirected there after reading the doc of IntegerVectors (for instance).

I am making no assumption. The user does not *need* to know about integer partitions. But if he does, he gets an additional hint.

I am fine making it into a SEEALSO if that's ok to put one before INPUT.

Works for me.

Ok, will do.

[nthiery]

Replying to aschilling:

Replying to jdemeyer:

I would prefer not to have integer_list_old in the reference manual. It's deprecated, you're not supposed to use it. So let's at least pretend that it doesn't exist.

I agree with this. Fixed!

Then we need to remove the dandling crosslink from integer_list as well (fixing this crosslink was the reason why I had inserted integer_list_old in the ref man). Done.

[git]

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

​238b3aa	17979: removed crosslink to integer_lists_old
​2e38ce4	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

[nthiery]

Replying to ncohen:

Nathann, is this OK for you?

I believe deciding on API changes like this is going beyond the scope of this ticket; we are taking decisions in a rush on things that are debatable (see the discussion with Vincent). But oh well, let's move on. Thanks Jeroen for taking action toward some state that is acceptable to everyone.

I would have changed the calls to make them use DisjointUnionEnumeratedSet directly, but if you think that this deserves a function then no proble.

I really would much prefer a direct use of DisjointUnionEnumeratedSet?, in particular to set an example for others that would need a similar feature.

Also, I spent a good deal of time working on documentation and tests that were just wiped out by this commit. The right thing to do is to recycle them whenever this can be useful, and at the very least adapt the tests. I'll work on this now.

Cheers,

Nicolas

PS: It's Pycon today; I'll see what I can do to handle the remaining comments by Nathann. In the mean time, it would be helpful if we could get comments on the rest (lookahead, Envelope, ...).

[jdemeyer]

Replying to nthiery:

I believe deciding on API changes like this is going beyond the scope of this ticket; we are taking decisions in a rush on things that are debatable

Also, I spent a good deal of time working on documentation and tests that were just wiped out by this commit. The right thing to do is to recycle them whenever this can be useful

Everything is still in the git history, you can always roll back my commit... (perhaps indeed after agreeing on a good API)

[jdemeyer]

Replying to nthiery:

Also, I spent a good deal of time working on documentation and tests that were just wiped out by this commit. The right thing to do is to recycle them whenever this can be useful, and at the very least adapt the tests.

Let me remark that the tests involving Partitions() didn't actually test what you claimed they tested (Partitions itself handles NN).

[jdemeyer]

Replying to nthiery:

at the very least adapt the tests.

I actually believe that I did that.

[git]

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

​37b8dd0

17979: recycled doc and tests deleted in 3363aeb30397b74178949e0d9fbba292e68b65c8

[nthiery]

Replying to jdemeyer:

Replying to nthiery:

at the very least adapt the tests.

I actually believe that I did that.

Two got removed (in the equality test). No worry, it was easy to recycle from the git history :-)

Thanks for detecting that Partitions was handling this on its own!

[nthiery]

Jeroen: is it ok if I switch to using DisjointUnionEnumeratedSets in Words / ... ?

For the API change: let's just move on; that will do.

[jdemeyer]

Replying to nthiery:

Jeroen: is it ok if I switch to using DisjointUnionEnumeratedSets in Words / ... ?

I would do it only for NN, not for the range.

[git]

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

​820526e

17979: Added TODO's about replacement of the IntegerListsNN calls to IntegerVectors + warning about its potential deletion

[nthiery]

Replying to nthiery:

Jeroen: is it ok if I switch to using DisjointUnionEnumeratedSets in Words / ... ?

I started doing this, and then realized that the two locations where we are using IntegerListsNN would be best written using IntegerVectors(length=..., ...). However this feature is broken (see #17927). So I switch gear: let's keep things are they are for now, switch to IntegerVectors in the upcoming #17927, and probably get rid of the temporary IntegerListsNN then.

I left TODO notes in the code.

[git]

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

​2f37527

17979: small wording improvement

[nthiery]

• In the following text which says that one can force the enumeration when it is formally impossible, can you explicitly say what will happen? "All possible lists are enumerated, but the ordering is incorrect" or something? If one wants to proceed anyway, one can sign a waiver by setting check=False:

It's mentioned just above:

the list ``[1, 1, 1]`` will never appear in the enumeration

Isn't this enough?

Btw: I just made minor improvements to the doc around there.

[nthiery]

• About this paragraph:

  The set of allowable constraints has been specifically designed to enable
  iteration with a good time and memory complexity in most practical use cases,
  and in inverse lexicographic order (see below)
  

I do not believe that it is true, i.e. that the set of allowable contraints has been specifically designed to enable iteration with a good time and memory complexity.

Well, this certainly was our design goal when we came up with it with Florent! I am not saying iteration with a good time and complexity is currently implemented, but I do believe this is possible in most practical use cases.

Anyway, just rephrase this to whatever you wish. I don't really care. Or more precisely I care more about this ticket being done.

In particular, it is possible to get great speed improvements by writing a Constant Amortized Time (CAT) Algorithm to list only partitions satisfying a smaller set of constraints like (sum,length,min/max part).

If you take the current algorithm, specialize the lookahead to be trivial (because, for plain partitions, the prediction is indeed trivial: any prefix can be extended to at least one integer partition), and avoid a copy of the result, you recover exactly the standard CAT algorithm for enumerating integer partitions in inverse lexicographic order.

In fact that's exactly how we came up with this design: by getting tired of reimplementing exactly the same CAT algorithm for integer partitions, compositions, and looking for some unifying context.

More precisely we are shooting for LAT (Linear Amortized Time): the iterator protocol is indeed not really favorable to pure CAT: if one yields a reference to the current list at each step, things are likely to break, unless the user makes an immediate read only use of it. So for now we assume that we make a copy of each list.

I am not claiming we can always achieve LAT. But I believe that we can get pretty close to it in the common use cases, which will qualify for "good time and memory complexity".

[nthiery]

Up to the aforementioned sentence that I let Nathann edit to his taste, I believe all the comments have been adressed one way or the other. Hence back to needs review.

[git]

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

​eda2471

trac #17979: Just some doc

[ncohen]

Hello,

Up to the aforementioned sentence that I let Nathann edit to his taste

I just did that. I added ten words to the sentence which mentions the argument 'check', and removed the part of the doc about the design of that class.

My idea of what an efficient implementation of this feature should be is closer to chapter 16 of the fxtbook [1].

In a previous message you mentionned #17927. Would anybody be willing to review it? It has been lying there for 4 weeks, and is now in conflict with the commits that have been added here since.

Nathann

[1] ​http://www.jjj.de/fxt/fxtbook.pdf

[nthiery]

Replying to ncohen:

I just did that. I added ten words to the sentence which mentions the argument 'check', and removed the part of the doc about the design of that class.

I just check the changes and am ok with me (I am keeping a mental note to reinsert the statement about the design when we will have provable arguments)

Where do we stand now? Are there things left that remain to review?

My idea of what an efficient implementation of this feature should be is closer to chapter 16 of the fxtbook [1].

Juste a note: the code for next in 16.2 is precisely how next worked in the previous implementation of IntegerListsLex? (except that we had more checks to handle the extra arguments).

Altogether, I don't think we are far from ftxbook. The only thing is that there remains to make sure that our code does specialize well in the trivial cases like plain partitions. And of course to make it into compiled code. Once we will be there, we should certainly compare to the ftxbook benchmarks.

In a previous message you mentionned #17927. Would anybody be willing to review it? It has been lying there for 4 weeks, and is now in conflict with the commits that have been added here since.

As I mentioned earlier, I volunteered to handle the merge and review of #17927, when this one will be done.

[ncohen]

Juste a note: the code for next in 16.2 is precisely how next worked in the previous implementation of IntegerListsLex? (except that we had more checks to handle the extra arguments).

Altogether, I don't think we are far from ftxbook.

The asymptotic complexity is not the only thing I had in mind when I pointed toward that book. For things as easy to enumerate as integer partitions (wiht min/max n, min/max part, min/max length) I believe that we should have Cython implementation (no Python needed). When called at C level, it would be infinitely faster to enumerate and filter permutations satisfying a given predicate. It also couldn't hurt if IntegerListsLex relied on it in thos simple cases.

Nathann

[vbraun]

As always: First it has to be correct, then you can make it fast.

[ncohen]

As always: First it has to be correct, then you can make it fast.

Of course. I was not trying to defend the idea of reimplementing this code in Cython right now. I was only discussing with Nicolas a paragraph of its documentation.

Nathann

[nthiery]

Replying to ncohen:

The asymptotic complexity is not the only thing I had in mind when I pointed toward that book.

Yes, I know! Same for me.

For things as easy to enumerate as integer partitions (wiht min/max n, min/max part, min/max length) I believe that we should have Cython implementation (no Python needed). When called at C level, it would be infinitely faster to enumerate and filter permutations satisfying a given predicate. It also couldn't hurt if IntegerListsLex relied on it in thos simple cases.

In summary, the plan is:

• Correct implementation of IntegerListsLex? (this ticket)
• Asymptotically good implementation (#18055)
• Cython/C/C++ implementation (#18056)
• Serious benchmarking to see whether it's worth having specialized implementations for the "trivial" cases, and use "filtering from trivial" for the small cases.

Cheers,

Nicolas

[aschilling]

Replying to nthiery:

Replying to ncohen:

The asymptotic complexity is not the only thing I had in mind when I pointed toward that book.

Yes, I know! Same for me.

For things as easy to enumerate as integer partitions (wiht min/max n, min/max part, min/max length) I believe that we should have Cython implementation (no Python needed). When called at C level, it would be infinitely faster to enumerate and filter permutations satisfying a given predicate. It also couldn't hurt if IntegerListsLex relied on it in thos simple cases.

In summary, the plan is:

• Correct implementation of IntegerListsLex? (this ticket)
• Asymptotically good implementation (#18055)

FYI, Bryan and I talked about the algorithm for #18055 yesterday at Berkeley!

[nthiery]

Hi!

Is there anything we can do to help the final steps of the review?

[tscrim]

I'm going to set this to positive review since it seems like there are currently no objections to the current state of the code, it is a definite improvement over the previous code, and we can always do more work later on on followup tickets (thus we can get the next version of Sage released).

[nthiery]

Oops, I hope Nathann was ok with merging this ticket as is. It's probably alright since it was looked over quite extensively, and it was costly to hold up 6.6 even more. Worst case we can change things in later tickets.

In any cases: thanks everybody for all the hard work implementing and reviewing this ticket! One less big issue in Sage. Yeah!

Cheers,

Nicolas

[vbraun]

Documentation doesn't build

[combinat ] /mnt/SSD1/mod_buildslave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/quickref.py:docstring of sage.combinat.quickref:72: WARNING: undefined label: sage.graphs (if the link has no caption the label must precede a section header)
Error building the documentation.
Traceback (most recent call last):
  File "/mnt/SSD1/mod_buildslave/sage_git/build/src/doc/common/builder.py", line 1626, in <module>
    getattr(get_builder(name), type)()
  File "/mnt/SSD1/mod_buildslave/sage_git/build/src/doc/common/builder.py", line 292, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/mnt/SSD1/mod_buildslave/sage_git/build/src/doc/common/builder.py", line 503, in _wrapper
    x.get(99999)
  File "/mnt/SSD1/mod_buildslave/sage_git/build/local/lib/python/multiprocessing/pool.py", line 558, in get
    raise self._value
OSError: [combinat ] /mnt/SSD1/mod_buildslave/sage_git/build/local/lib/python2.7/site-packages/sage/combinat/integer_list.py:docstring of sage.combinat.integer_list.IntegerListsLex:151: ERROR: Unexpected indentation.

[tscrim]

I think I caught the error. Rebuilding doc now... (someone with a potentially faster computer, also do so).

---

Last 10 new commits:

​2380fd4	17979: safe if not perfect implementation of equality tests
​0bff449	17979: minor improvement to the doc of limit_start
​238b3aa	17979: removed crosslink to integer_lists_old
​3363aeb	Deprecate IntegerListsLex(n) where n is an iterable
​2e38ce4	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex
​37b8dd0	17979: recycled doc and tests deleted in 3363aeb30397b74178949e0d9fbba292e68b65c8
​820526e	17979: Added TODO's about replacement of the IntegerListsNN calls to IntegerVectors + warning about its potential deletion
​2f37527	17979: small wording improvement
​eda2471	trac #17979: Just some doc
​16f21fc	Some tweaks, hopefully the doc builds.

[git]

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

​9a34379	17979 fixed glitch with documentation build
​75f32a0	Merge branch 'public/ticket/17979' of git://trac.sagemath.org/sage into public/ticket/17979

[git]

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

​5441737	17979: ReST fix
​ea2b006	Merge branch 'public/ticket/17979' of trac.sagemath.org:sage into combinat/integer_lists_lex

[tscrim]

Okay, Nicolas and I found the issue (simultaneously but independently with Anne). Nicolas did a full doc rebuild, which returned clean. So back to positive review.

[jdemeyer]

Good that this is now merged. I think the next steps should be doing some of the cleanup mentioned here. In particular:

• Stop using global_options
• Remove integer_list_old.py
• Get rid of element_constructor

[nthiery]

Replying to jdemeyer:

Good that this is now merged. I think the next steps should be doing some of the cleanup mentioned here. In particular:

• Stop using global_options

IntegerListsLex? is not really using it. Just passing it on for other classes that need it. But if there is a way to refactor those classes to not impose this burden on IntegerListsLex?, that would be better indeed.

• Remove integer_list_old.py

Yes, at the end of #18055.

• Get rid of element_constructor

We probably want to change the default value. But we certainly want to keep the feature.

Cheers,

Nicolas

[nthiery]

Replying to jdemeyer:

I disagree with this. I think code duplication is always a high risk for bugs.

This gave me a good laugh: usually people complain at me for tending to overdesign to remove the very last duplicated bit :-)

[jdemeyer]

Replying to nthiery:

• Remove integer_list_old.py

Yes, at the end of #18055.

How is #18055 related to removing integer_list_old.py???

[nthiery]

See 446

[jdemeyer]

I see your point. What I really meant is: stop using integer_list_old.py in the Sage library (it's still used by integer_vector.py).

[nthiery]

Replying to jdemeyer:

I see your point. What I really meant is: stop using integer_list_old.py in the Sage library (it's still used by integer_vector.py).

Oh, I see. This requires a small additional feature (initializing the iterator from a specified prefix instead of []) which should be easy to add, typically as part of #18055 unless someone wants to jump in before.