#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 | e151d78ea32b9cac2047e2faff3247bdcce1f5d5
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Hello,
This is what I did during the last 3~4 hours. I stopped before the end and
did
not review `m_interval`, `_lookahead` nor the code of `Envelope`, as I
really
should be working on mathematics instead of Sage `T_T`
Some are easy, some are harder. Also, let me write somewhere that I am
against
keeping `integer_list_old` in Sage, as I am afraid that it will still be
here
several years from now. Here are my comments:
- Module documentation -- in the 'itemize' section listing
`IntegerListsLex` and
`Envelope`, could you add a short description of what they are meant
for?
- Why a 'history' section?
- Documentation of `IntegerListsLex`: instead of stating the *purpose* of
the
class (which is more something one would explain on a trac ticket), what
about
a SEEALSO section? I have the following paragraph in mind:
{{{
The main purpose is to provide a generic iteration engine for all
the enumerated sets like :class:`Partitions`,
class:`Compositions`, :class:`IntegerVectors`. It can also be
used to generate many other combinatorial objects like Dyck paths,
Motzkin paths, etc.
}}}
I thought that it would make more sense as a SEEALSO section pointing
toward
the mentionned objects.
- About this paragraph:
{{{
The set of allowable constraints has been specifically designed to
enable
iteration with a good time and memory complexity in most practical use
cases,
and in inverse lexicographic order (see below)
}}}
I do not believe that it is true, i.e. that the set of allowable
contraints
has been specifically designed to enable iteration with a good time and
memory
complexity.
In particular, it is possible to get great speed improvements by writing
a
Constant Amortized Algorithm to list only partitions satisfying a
smaller set
of constraints like (sum,length,min/max part).
This statement sounds wrong to me, and so I believe that it should be
removed.
- Documentation of the parameter `n` -- you say that a list of integers
can be
provided but do not explain what the output will be.
- Are `min_sum` and `max_sum` also ignored when `n` is a list? From the
doc it
seems to be, though I am not sure that it is the best design choice in
this
case.
- I was surprised by the following output:
{{{
sage: IntegerListsLex(3,max_length=3,floor=[1,1,1]).list()
[[3], [2, 1], [1, 2], [1, 1, 1]]
}}}
I woud have expected the length of the lists to be at least 3, as I
requested
the first three parts to be `>=1`. The documentation is consistent, but
I
still find it surprising.
- ``check`` seems misnamed. It is not about checking the input or output,
only
about displaying warnings. What about `disable_warnings` instead?
- In the following text which says that one can force the enumeration when
it is
formally impossible, can you explicitly say what will happen? "All
possible
lists are enumerated, but the ordering is incorrect" or something?
{{{If one wants to proceed anyway, one can sign a waiver by setting
check=False:}}}
- About the finiteness check: what about a specific
`allow_infinite_iterator`
independent from the current 'check'.
- Building the doc of `integer_list.py` with `--warn-links` fails.
- {{{sage: list(IntegerListsLex(3, max_length=2, ))}}}
- Lexicographic ordering is broken when `n` is a list.
{{{
sage: print IntegerListsLex([1,2],length=3).list()
[[1, 0, 0], [0, 1, 0], [0, 0, 1], [2, 0, 0], [1, 1, 0], [1, 0, 1], [0,
2, 0], [0, 1, 1], [0, 0, 2]]
}}}
In particular, the output differs depending on how `n` is sorted.
- Cardinality is broken when `n` is a list
{{{
sage: IntegerListsLex(3,length=3).cardinality()
10
sage: IntegerListsLex([3,3],length=3).cardinality()
20
}}}
- {{{return typecall(cls, n=n, **kwargs)}}} -- for clarity I find the
normal
syntax better. This place is not a critical part for speed, especially
when
you create `DisjointUnionEnumeratedSets` with lambda functions just
above.
- I had not noticed that `IntegerListsLex` objects could have a 'name'
argument.. As all arguments, it must be documented in the INPUT section.
- Same for `element_constructor` and `element_class`.
- {{{self._max_length = ZZ(max_length) if max_length != Infinity else
max_length}}}
Just my two cents: I would return 'Infinity' instead of max_length. You
defined your `Infinity` in order to be fast, and you don't know what
`max_length` may be. This occurs several times.
- You can save space and turn the two following tests into one (using the
same
'all'). Occurs twice.
{{{
if not all(i in ZZ for i in floor):
raise TypeError("the parts of floor={} should be nonnegative
integers".format(floor))
if not all(i >= 0 for i in floor):
raise NotImplementedError("negative parts in
floor={}".format(floor))
}}}
This would also solve the following, which tests `ceiling` but mentions
`floor`
{{{
if not all(i >= 0 for i in ceiling):
raise NotImplementedError("negative parts in
floor={}".format(ceiling))
}}}
- {{{# constructor is known to be safe and don't claim ownership on}}} --
"does
not".
- Typing `IntegerListsLex.<tab>` in the console is very entertaining. I
would be
very glad if we some day decide to consider this as a bug.
- about `check_finiteness` -> what about `guess_finiteness` instead, to
emphasize that the function makes mistakes?
- The error message when the set is infinite is misleading:
{{{
sage: L = IntegerListsLex(4)
sage: L._check_finiteness()
...
ValueError: Could not check that the specified constraints yield a
finite set
}}}
The code was able to perform the check, though it was not "able to
decide that
the set is finite".
- I do not understand this comment:
{{{If a part has no bound on its value, it will be detected at some
point}}}
Do you mean that "at some point in __iter__" it will be detected?
Probably
not, as this function is called only once.
- The function `_check_finiteness` assumes that the alphabet size is
bounded. It
is always true when this function is called, but the following raises no
warning:
{{{
sage: for x in IntegerListsLex(NonNegativeIntegers(),max_length=3):
....: pass
}}}
For the reason given earlier, the output is not sorted
lexicographically. It
is not detected as infinite either.
- The many `if A: return` from `_check_finiteness` can be replaced by a
`if A or
B or C or ...: return`.
- in `_check_finiteness`: the documentation of `limit()` says that it is
only an
upper bound. Thus you cannot write the following:
{{{
if self._ceiling.limit() < self._floor.limit():
return
}}}
- Same comment here
{{{
if self._floor.limit() > 0 or self._min_slope > 0:
floor_sum_lower_bound = Infinity
}}}
- Also, it seems that `limit_start()` can be `Infinity`, in which case one
cannot deduce anything from the value of `limit`. Please add checks.
- I stop reviewing `_check_finiteness`, as it is complicated while the
situation
of `limit()` is not cleared.
- {{{Which specific bound is returned is not set in stone}}}. Be more
accurate.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17979#comment:412>
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.
