#17979: Reimplementation of IntegerListsLex
-------------------------------------+-------------------------------------
Reporter: aschilling | Owner:
Type: defect | Status: needs_work
Priority: blocker | Milestone: sage-6.6
Component: combinatorics | Resolution:
Keywords: days64 | Merged in:
Authors: Bryan Gillespie, | Reviewers:
Anne Schilling, Nicolas M. Thiery | Work issues: support n in an
Report Upstream: N/A | iterable
Branch: | Commit:
public/ticket/17979 | 6153cf8d39dc23cb41a3d0c2ea66ba5dc3abd2c0
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by bgillespie):
Replying to [comment:27 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.
[[BR]]
> - {{{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.
[[BR]]
> - 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.
[[BR]]
>
> - `Lower and upper bounds`: the text about constant values for
floor/ceiling
> belongs to the INPUT block.
Updated.
[[BR]]
> - `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.
[[BR]]
> - `Next we obtain all lists of sum 4 and length 4 such that l[i] <= i:`
--
> missing backticks at the end.
Fixed.
[[BR]]
> - 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.
[[BR]]
> - There are two 'TESTS' sections
That is true. Fixed.
[[BR]]
> - {{{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.
[[BR]]
> - 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.)
[[BR]]
> - 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.
[[BR]]
> - 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.
>
> {{{
> #!diff
> -# Copyright (C) 2007 Mike Hansen <[email protected]>,
> -# Copyright (C) 2012 Travis Scrimshaw <[email protected]>
> +# Copyright (C) 2015 Bryan Gillespie <[email protected]>,
> }}}
The update is a complete rewrite, so probably a new author list makes
sense.
-- Bryan
--
Ticket URL: <http://trac.sagemath.org/ticket/17979#comment:65>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
