我们研究了长度为 $n$ 的排列的精确均匀采样问题，这些排列的最长递增子序列（LIS）具有指定的长度 $k$。我们的主要结果是，至今为止，我们首次提出了针对该问题的多项式时间精确采样器，适用于每个 $1 \le k \le n$。通过罗宾逊-申斯特德对应关系，该问题简化为从钩长平方（条件普朗切雷尔）法则中采样首行长度为 $k$ 的杨图。
我们逐个坐标地采样这种形状，其中每个条件权重，作为对指数多个补全的求和，通过考希-比奈特公式简化为小多项式矩阵的行列式的单个系数。直接实现的期望时间为 $\tilde O(n^4k^5)$，在字-随机存取存储器模型中。利用评估矩阵的汉克尔结构将其减少到 $\tilde O(n^3k^4)$。
在 $k \in \Theta(n)$ 的线性范围内，我们给出了一个直接的拒绝采样器，期望时间为 $O(n\log\log n)$，与计算一个排列的 LIS 的成本相匹配（至常数）。对于放宽约束 $LIS(\pi) \le k$，普通拒绝采样在每个 $k \ge 4\sqrt n$ 的情况下给出期望时间 $O(n\log\log n)$，因此所有 $k$ 的最坏情况时间改善为 $\tilde O(n^5)$。
博主点评： 本文提出的多项式时间精确采样器为处理具有固定 LIS 的排列问题提供了全新的视角，利用了强大的组合数学工具，并且在实际应用中表现出色，特别是在大规模数据集上的效率提升令人瞩目。该方法的实现细节与复杂度分析值得深入研究，具有广泛的应用潜力。