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.

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

[videlec]

comment:6

Apparently yes : https://en.wikipedia.org/wiki/Longest_increasing_subsequence

[dcoudert]

comment:7

Indeed for a single sequence. Not sure how to extend to find all longest sequences.

[videlec]

comment:8

Replying to @dcoudert:

Indeed for a single sequence. Not sure how to extend to find all longest sequences.

There could be exponentially many longest sequences. Pick p = [2,1,4,3,6,5,...,2n,2n-1]. Then there are 2^n longest increasing sequences (they are of length n). Note that building the automaton that stores them all is what Nadia proposed in #31451. Not sure about complexity, but it is for sure polynomial.

It would be interesting to implement something fast to count the number of such sequence. This could be obtained for example from #31451 as the coefficient (0,n+1) of the n+1-th power of the adjacency matrix of D.

[vbraun]

Changed branch from public/combinat/34214 to 15aa550