Reimplementation of IntegerListsLex

[aschilling]

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

See also #18055 and #18056 for followups.

Remaining design points:

• Renaming all the attributes (.floor, ...) to private attributes
• Double check the logic for improper lexicographic iterability detection

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