Faster version of longest_increasing_subsequence_length

[dcoudert]

Before

sage: set_random_seed(0)
sage: P = Permutations(30)
sage: L = [P.random_element() for _ in range(1000)]
sage: %timeit [e.longest_increasing_subsequence_length() for e in L]
24.9 ms ± 953 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

After

sage: %timeit [e.longest_increasing_subsequence_length(e) for e in L]
5.94 ms ± 133 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

follow up: #31451, #34218

CC: @videlec @nadialafreniere

Component: combinatorics

Keywords: permutation, subsequences

Author: David Coudert

Branch/Commit: 15aa550

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/34214

[dcoudert]

Branch: public/combinat/34214

[dcoudert]

Commit: 2e183cf

[dcoudert]

New commits:

2e183cf

trac #34214: faster longest_increasing_subsequence_length

[sagetrac-git]

Changed commit from 2e183cf to 15aa550

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

15aa550

trac #34214: remove a useless variable

[dcoudert]

comment:3

Roughly, we replace the calls to max, min and index by a single call to bisect. The time complexity of the method is now O(n log(n)).

[dcoudert]

comment:4

Green bot.

[dcoudert]

Description changed:

--- 
+++ 
@@ -10,7 +10,7 @@
 After
 
 ```
-sage: %timeit [longest_increasing_subsequence_length_v2(e) for e in L]
+sage: %timeit [e.longest_increasing_subsequence_length(e) for e in L]
 5.94 ms ± 133 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
 ```
 

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:5

This is indeed cleaner.

The algorithm is clever. Do you know if it possible to generate such subsequence in O(n log n) ? In the data generated by the algo, only r[-1] is guaranteed to be the last element of a longest increasing subsequence.