#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: Nathann Cohen, Jeroen
Anne Schilling, Nicolas M. Thiery | Demeyer, Travis Scrimshaw
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/ticket/17979 | 2380fd4fcf61347f9b86ee09f7488dac7e1d9fe2
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by 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
--
Ticket URL: <http://trac.sagemath.org/ticket/17979#comment:437>
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.
