Opened 4 years ago

# Improve lookahead in IntegerListsLex — at Version 7

Reported by: Owned by: nthiery major sage-6.6 combinatorics bgillespie 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 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. Using dichotomy on the area / parts, it should be possible to achieve good complexity in most cases.

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).
• Remove `integer_list_old` at the final stage.

### comment:1 Changed 4 years ago by aschilling

• Description modified (diff)

### comment:2 Changed 4 years ago by aschilling

• Description modified (diff)

### comment:3 Changed 4 years ago by nthiery

• Description modified (diff)

### comment:4 Changed 4 years ago by nthiery

• Description modified (diff)

### comment:5 follow-up: ↓ 6 Changed 4 years ago by jdemeyer

• Description modified (diff)

Can we please stop talking about "degenerate cases" without specifying what that means?