Faster version of longest_increasing_subsequences

[petermoraw]

The algorithm for the longest_increasing_subsequences function for permutations is currently very inefficient. I worked on a new version that vastly improves the run time of the function.
New version:

sage: %timeit Permutations(30).random_element().longest_increasing_subsequences()                                     
19.6 ms ± 2.28 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Old version:

sage: %timeit Permutations(30).random_element().longest_increasing_subsequences()                                     
The slowest run took 10.40 times longer than the fastest. This could mean that an intermediate result is being cached.
3min 34s ± 2min 47s per loop (mean ± std. dev. of 7 runs, 1 loop each)

follow-up: #34218

CC: @nadialafreniere @enadeau @tscrim

Component: combinatorics

Keywords: permutation, subsequences

Author: Peter Morawitz, Finn Hulse, Nadia Lafrenière

Branch/Commit: 5969eda

Reviewer: David Coudert, Vincent Delecroix

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

[petermoraw]

Branch: u/gh-petermoraw/LongestIncreasingSubsequences

[nadialafreniere]

New commits:

c65429f	improved longest increasing subsequences function
0bb729e	Added reference

[nadialafreniere]

Commit: 0bb729e

[fchapoton]

comment:3

• when citing a reference, you should append an underscore, like this

[Sch1961]_

• Do not use "Returns" in the first line of doc, but "Return"

[fchapoton]

comment:4

and patchbot complains about

src/doc/en/reference/references/index.rst  # Tab character found

[tscrim]

comment:6

I think seq == sorted(seq) would be better replaced by

all(seq[i] <= seq[i+1] for i in range(len(seq)-1))

Also, is there a way you can avoid all of the calls to index here:

self.index(seq[j]) < self.index(seq[j+1]):

I feel like there should be a better way to track things, otherwise this could run in O(len(seq)^2) (maybe O(log(len(seq)*len(seq))) time.

You can remove this useless list

-        potential_sequences = list(itertools.product(*s))
-        for seq in potential_sequences:
+        for seq in itertools.product(*s):

I think it is cleaner to write j += 1 instead of j = j+1. It might also be marginally faster.

[sagetrac-git]

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

86204b5

tscrim edits

[sagetrac-git]

Changed commit from 0bb729e to 86204b5

[fchapoton]

comment:8

you still have not fixed comment:3 and comment:4

[tscrim]

comment:9

Nor have you commented on why you did not implement all of the suggestions from comment:6.