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?

### comment:6 in reply to: ↑ 5 Changed 4 years ago by nthiery

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

This ticket involves some research, which includes in particular defining precisely what "degenerate" is. Until this research is done, we can't do anything but remain vague.

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

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