Opened 8 years ago

# Improve lookahead in IntegerListsLex — at Version 3

Reported by: Owned by: Nicolas M. Thiéry major sage-6.6 combinatorics Bryan Gillespie N/A

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

### comment:1 Changed 8 years ago by Anne Schilling

Description: modified (diff)

### comment:2 Changed 8 years ago by Anne Schilling

Description: modified (diff)

### comment:3 Changed 8 years ago by Nicolas M. Thiéry

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