Opened 8 years ago

Last modified 8 years ago

## #18055 new enhancement

# Improve lookahead in IntegerListsLex — at Version 3

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: |

### Description (last modified by )

`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.

Concrete steps:

- Extend
`Envelope`

with a function:def area(k): """Return the area under the envelope between `0` and `k`"""

This functions should handle the "reverse smoothing" from position

`k`

(so that the envelope satisfies both`min_slope`

and`max_slope`

conditions between`1`

and`k`

), and have appropriate algorithmic and caching so that the overall complexity of computing all`area(k)`

for`k<=l`

is linear in`l`

.

- Replace:
def _possible_m(self, m, ...):

by:def lookahead(self):

which shall detect whether

`_current_list`

has a chance to be a prefix of some valid list. Using the above`area`

method of the envelopes, it should be possible to detect most dead branches.

This method should support

`_current_list=[]`

as well.

This method should store as much information as relevant to avoid later recomputation for lower nodes in the tree. A minima, this could possibly return/store a range for the next value, removing the need for a separate

`_m_interval`

method.

- Update
`next`

accordingly (the logic should be slightly simpler thanks to the handling of the empty prefix).

### Change History (3)

### comment:1 Changed 8 years ago by

Description: | modified (diff) |
---|

### comment:2 Changed 8 years ago by

Description: | modified (diff) |
---|

### comment:3 Changed 8 years ago by

Description: | modified (diff) |
---|

**Note:**See TracTickets for help on using tickets.