We study the exact uniform sampling of permutations of length $n$ whose longest increasing subsequence (LIS) has a prescribed length $k$. Our main result is, to the best of our knowledge, the first polynomial-time exact sampler for this problem, valid for every $1 \le k \le n$. Via the Robinson–Schensted correspondence, the problem reduces to sampling a Young diagram with the first row of length $k$ from the hook-length-squared (conditioned Plancherel) law.
We sample this shape one coordinate at a time, where each conditional weight, a sum over exponentially many completions, collapses, through the Cauchy–Binet formula, to a single coefficient of the determinant of a small polynomial matrix. A direct implementation runs in expected $\tilde O(n^4k^5)$ time in the word-RAM model. Exploiting the Hankel structure of the evaluated matrices reduces this to $\tilde O(n^3k^4)$.
In the linear regime $k \in \Theta(n)$, we give a direct rejection sampler running in expected $O(n\log\log n)$ time, matching, up to constants, the cost of computing the LIS of one permutation. For the relaxed constraint $LIS(\pi) \le k$, plain rejection sampling gives expected $O(n\log\log n)$ time for every $k \ge 4\sqrt n$, and so the worst case over all $k$ improves to $\tilde O(n^5)$.
Blogger's Review: The polynomial-time exact sampler proposed in this paper offers a fresh perspective on handling permutations with fixed LIS, leveraging powerful combinatorial tools. Its performance, particularly in improving efficiency on large datasets, is remarkable. The implementation details and complexity analysis are worth exploring, showcasing broad potential applications.