Opened 8 years ago

Last modified 8 years ago

#18055 new enhancement

Improve lookahead in IntegerListsLex — at Version 2

Reported by: Nicolas M. Thiéry Owned by:
Priority: major Milestone: sage-6.6
Component: combinatorics Keywords:
Cc: Bryan Gillespie Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Anne Schilling)

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()

The following also take a long time, which should be optimized:

    sage: IntegerListsLex(10^100, max_length=1).list()
    sage: IntegerListsLex(499499, length=1000, 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 (2)

comment:1 Changed 8 years ago by Anne Schilling

Description: modified (diff)

comment:2 Changed 8 years ago by Anne Schilling

Description: modified (diff)
Note: See TracTickets for help on using tickets.