Opened 5 years ago

Last modified 5 years ago

#18055 new enhancement

Improve lookahead in IntegerListsLex — at Initial Version

Reported by: nthiery Owned by:
Priority: major Milestone: sage-6.6
Component: combinatorics Keywords:
Cc: bgillespie Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

IntegerListsLex uses a depth first search in a prefix tree, with lookahead to prune branches. The purpose of this ticket is to improve the lookahead algorithm in two directions:

  • Detect more branches that can be cut.
  • Better time complexity; this probably will involve identifying important invariants and caching them.

Example:: even just for n=1000 this is taking a long time:

    sage: n = 100
    sage: IntegerListsLex(binomial(n,2)-1, length=n, min_slope=1).list()

One could hope that, in non degenerate cases, one could reach an average complexity roughly linear in O(log(max_n), max_length) per list generated.

Change History (0)

Note: See TracTickets for help on using tickets.