#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 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
--
Ticket URL: <http://trac.sagemath.org/ticket/17979#comment:52>
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.
