#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 nthiery):
Replying to [comment:52 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)
In fact, the point of the algorithm is that there *is* guessing on the
future; in most not-too-degenerate cases, one can detect that a branch
will lead to nowhere and cut it.
> 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.
At this point, the complexity of the following is not linear as it
ought to be (one should be able to do the detection work faster by
caching critical data), but it definitely is polynomial with a small
degree (most likely quadratic), and very far from 2^n:
{{{
sage: n=20; IntegerLists(n, length=n,max_part=1).list()
sage: n=1000
sage: %time IntegerListsLex(n, length=n,max_part=1).list()
CPU times: user 852 ms, sys: 25.5 ms, total: 877 ms
Wall time: 831 ms
sage: n=2000
sage: %time x = IntegerListsLex(n, length=n,max_part=1).list()
CPU times: user 3.15 s, sys: 24.2 ms, total: 3.17 s
Wall time: 3.15 s
}}}
Cheers,
Nicolas
--
Ticket URL: <http://trac.sagemath.org/ticket/17979#comment:63>
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.
