如何排序{1,2,…,M}的排列以实现O(M)时间的rank()与unrank()函数？

核心排序逻辑：基于Lehmer码的阶乘序排列 #

我们需要让集合{1,2,...,M}的排列按照阶乘序排列——每个排列的索引（rank）与其对应的Lehmer码的十进制值严格对应。Lehmer码是一个长度为M的序列L=[l₁,l₂,...,l_M]，其中l_i∈{0,1,...,M-i}，表示排列第i位元素是当前剩余未选元素中的第l_i小的元素（从0开始计数）。

1. rank()函数（O(M)时间实现） #

步骤：

• 预计算阶乘数组：提前算出fact = [0!,1!,...,(M-1)!]，这一步时间复杂度为O(M)。
• 用并查集维护剩余元素：初始化并查集parent[x] = x（代表元素x未被使用），通过路径压缩快速查询未被使用元素中比当前元素小的数量。
• 遍历计算rank：
  1. 初始化rank = 0。
  2. 对排列P的每个元素p_i（从左到右）：
     • 查询未被使用元素中小于p_i的数量，记为l_i。
     • 执行rank += l_i * fact[M-i]。
     • 标记p_i为已使用（将p_i的父节点指向p_i+1，实现后续查询时跳过已用元素）。
  3. 最终得到的rank就是排列P的索引位置。

2. unrank()函数（O(M)时间实现） #

步骤：

• 预计算阶乘数组：同rank()的准备工作，提前生成fact数组。
• 将索引转换为Lehmer码：
  1. 初始化剩余索引为给定的index。
  2. 对每个位置i（从1到M）：
     • l_i = index // fact[M-i]
     • index = index % fact[M-i]
     • 保存l_i到Lehmer码数组中。
• 用并查集生成排列：
  1. 初始化并查集维护未被使用的元素。
  2. 对每个l_i：
     • 定位到第l_i+1个未被使用的元素，作为排列的第i位。
     • 标记该元素为已使用（更新并查集）。
  3. 最终得到的序列就是对应索引的排列。

时间复杂度说明 #

并查集的查询、更新操作经过路径压缩后，均摊时间复杂度为近似O(1)。加上预计算阶乘的O(M)时间，整个rank()和unrank()的时间复杂度可视为O(M)（忽略常数因子）。

内容的提问来源于stack exchange，提问作者some_guy256