#17898: Removal of wrong stopgap
-------------------------------------+-------------------------------------
Reporter: aschilling | Owner:
Type: defect | Status: needs_work
Priority: major | Milestone: sage-6.6
Component: combinatorics | Resolution:
Keywords: stopgap, | Merged in:
partitions | Reviewers: Travis Scrimshaw
Authors: Anne Schilling | Work issues:
Report Upstream: N/A | Commit:
Branch: | 39142901893bc0207e8271ccd4772469fe958e0f
public/ticket/17898 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by ncohen):
* cc: vdelecroix, jdemeyer (added)
* status: positive_review => needs_work
Comment:
Hello everybody,
Sorry to interrupt, but I believe that what is being done by this code is
not
advisable for Sage. You make several points in the ticket's description
that I
will now try to answer.
The function `IntegersListsLex` returns unexpected results
1) Indeed, as shown on #17637, one can get:
{{{
sage: Partitions(5, min_slope=1).list()
ValueError: [2, 4] is not a valid partition
sage: IntegerListsLex(5, length=3, max_slope=0).list() # 0 is
allowed in the partition
[[5, 0, 0], [4, 1, 0], [3, 2, 0], [3, 1, 1], [2, 2, 1]]
sage: IntegerListsLex(5, max_slope=0).list() # now its not
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1,
1]]
}}}
2) Another example comes from the documentation of `IntegersListsLex`
itself
{{{
In the following example, the slope condition is not satisfied
by the upper bound on the parts, and ``[3,3]`` is erroneously
included in the result::
sage: list(IntegerListsLex(6, max_part=3, max_slope=-1))
[[3, 3], [3, 2, 1]]
}}}
Returning wrong results should be considered as a bug
The fact that the docstring of this function reads that "several
constraints
must be satisfied, lest the input be incorrect" is not a sufficient
protection.
1) This function can (and is) called by other functions. Thus, users
cannot
be expected to read the documentation of `IntegerListsLex`.
2) In general, a simple line in the documentation in a function is not
a
sufficient protection against wrong results. This is the reason why
these
'stopgap' tickets exist.
3) It took me a couple of hours to realise that I was not able to
write a
code that checks that the input of `IntegerListsLex` is
satisfiable. I
take it as a proof that checking it is non-trivial (at least for
me). I
cannot expect users to check something that I am not able to check
myself.
Some functions which call `IntegerListsLex` are actually correct
I agree with you that in some cases the `IntegersListsLex` function
seems to
return correct results. This is not, however, a sufficient reason to
remoe a
stopgap whose purpose is to warn users against *possible* wrong
results.
An alternative way out
As I understand that you may be bothered by those warnings, which
appear in
any function that calls `IntegersListsLex` and thus in your code too,
perhaps you could go over some of the use cases of `IntegerListsLex`
that
are of interest to you, and only remove the stopgap message after you
have
convinced yourself that the function is indeed correct in these
situations?
{{{
if (some_situation_that_was_checked):
pass
else:
<stopgap code>
}}}
The message would still be shown in other (unchecked) cases, and thus
only
in dangerous situations.
A long-term fix
As you say in this ticket's description, a real check should be
implemented
at the head of `IntegerListsLex`, or it should be reimplemented.
I gave the first option a try already, and I remember rather well the
knots
it made in my head, as I was going over all ways in which the
parameters can
be combined. Checking that they are consistent is nontrivial.
It got me convinced that this function already accepts an unhealthy
amount
of parameters, and that we will not be able to write a function that
handles
all that efficiently and correctly. I believe that we should split
this
function into many, that will handle well each combination of
parameters
that interests us.
If possibly in Cython, for the most useful computations. That would
not be a
terribly hard work, in particular for your own code which (I believe)
enumerates only partitions.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17898#comment:3>
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.
