Implement longest_increasing_subsequence_number

[videlec]

Following the method of #31451, we implement a method that returns the number of maximal increasing subsequences of a permutation. This method is much faster than listing them all

sage: %time _ = sum(len(p.longest_increasing_subsequences()) for p in Permutations(8))
CPU times: user 1.76 s, sys: 2.97 ms, total: 1.76 s
Wall time: 1.77 s
120770
sage: %time sum(p.longest_increasing_subsequences_number() for p in Permutations(8))
CPU times: user 328 ms, sys: 0 ns, total: 328 ms
Wall time: 328 ms
120770

Depends on #31451
Depends on #34214

CC: @nadialafreniere @dcoudert

Component: combinatorics

Author: Nadia Lafrenière, Vincent Delecroix

Branch/Commit: 11e2592

Reviewer: David Coudert

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

[nadialafreniere]

Branch: u/nadialafreniere/implement_longest_increasing_subsequence_number

[nadialafreniere]

Commit: cee005d

[nadialafreniere]

comment:2

I tried implementing it, but I'm not convinced by the result. The method with the adjacency matrix of the digraph seems to be slower. Mainly, I think that a lot of the problem comes from taking the exponential of the adjacency matrix of the digraph (an (n+2)-by-(n+2) matrix raised to a power that is in θ(√n) in average), and this seems to slow the process down much more than listing the longest increasing subsequences.

After coding it, I got the following times:

sage: %timeit len(Permutations(100).random_element().longest_increasing_subsequences())  # Naive 
2.8 ms ± 284 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: %timeit Permutations(100).random_element().longest_increasing_subsequences_number()  # new code
4.42 ms ± 42 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Even though I'm uploading my code to the trac, I think we might want to give up on the project. Or, if you know of a way to make it efficient, I would love to see it.

---

Last 10 new commits:

98030ff	Implementation of digraph strategy for Longest Increasing Subsequences
8d1c1d6	Fixing a bug with n=0 for longest increasing subsequences
62b9a39	Simplified end of code for longest increasing subsequences
4a7f5c8	Use of bisect for columns in longest_increasing_subsequences
5969eda	proper formatting for longest_increasing_subsequences
a5c59f3	Merge branch 't/31451/LongestIncreasingSubsequences' into t/34218/implement_longest_increasing_subsequence_number
2e183cf	trac #34214: faster longest_increasing_subsequence_length
15aa550	trac #34214: remove a useless variable
c897f83	Merge branch 't/34214/public/combinat/34214' into t/34218/implement_longest_increasing_subsequence_number
cee005d	Implemented longest_increasing_subsequences_number()

[videlec]

comment:3

Indeed, matrix powering is not clever enough. Though one can avoid the creation of the digraph which is time consuming.

---

New commits:

9b946a6

faster p.longest_increasing_subsequeces_number

[videlec]

Changed branch from u/nadialafreniere/implement_longest_increasing_subsequence_number to public/34218

[videlec]

Author: Nadia Lafrenière, Vincent Delecroix

[videlec]

Changed commit from cee005d to 9b946a6

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a98a60f

faster p.longest_increasing_subsequences_number

[sagetrac-git]

Changed commit from 9b946a6 to a98a60f

[videlec]

comment:5

At commit a98a60f I got

sage: %time sum(len(p.longest_increasing_subsequences()) for p in Permutations(8))
CPU times: user 1.76 s, sys: 2.97 ms, total: 1.76 s
Wall time: 1.77 s
120770
sage: %time sum(p.longest_increasing_subsequences_number() for p in Permutations(8))
CPU times: user 328 ms, sys: 0 ns, total: 328 ms
Wall time: 328 ms
120770

[videlec]

comment:6

And same test as your comment:2 gives on my machine

sage: %timeit len(Permutations(100).random_element().longest_increasing_subsequences())  # Naive 
1.55 ms ± 69.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
sage: %timeit Permutations(100).random_element().longest_increasing_subsequences_number()  # new code
122 µs ± 2.38 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

[dcoudert]

comment:9

I was about to explain how to count the number of paths on a DAG when all arcs go from level i to level i+1 in time O(|V| + |E|), but your solution avoids the creation of the DAG. This is smart.

You could add a little explanation of the algorithm, at least for Nadia.

For the documentation, you could use :meth:~.longest_increasing_subsequences, or something like that.

Otherwise, LGTM.

[dcoudert]

comment:10

For Nadia: roughly, in the DAG, the number of paths to reach vertex x of column i+1 is the sum over the predecessors of x (all in column i) of the number of paths from to source to each of these predecessors. For initialization, there is a single path to go from the source to a vertex in column 0 (a successor of the source). then, you iterate over the columns and you add the count of x in the current column to each of its successors.

The method of Vincent do the same computation but avoids to build the DAG.

[sagetrac-git]

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

88676d8	optimization and typing
11e2592	more documentation

[sagetrac-git]

Changed commit from a98a60f to 11e2592

[dcoudert]

comment:12

LGTM.

[dcoudert]

Reviewer: David Coudert

[nadialafreniere]

comment:13

Replying to @dcoudert:

For Nadia: roughly, in the DAG, the number of paths to reach vertex x of column i+1 is the sum over the predecessors of x (all in column i) of the number of paths from to source to each of these predecessors. For initialization, there is a single path to go from the source to a vertex in column 0 (a successor of the source). then, you iterate over the columns and you add the count of x in the current column to each of its successors.

The method of Vincent do the same computation but avoids to build the DAG.

Nice job! This looks very good!

[vbraun]

Changed branch from public/34218 to 11e2592