排列逆序编码与字典序编号

排到第 $i$ 位时，已经用过的元素都不能再出现。剩余元素中，比 ${\pi }_i$ 小的恰好有 $c_i$ 个，它们最终都在右边。因此 $c_i$ 记录当前元素在“剩余列表”中的零起点名次。

解码时，从 $[1,\dots ,n]$ 开始，第 $i$ 步列表长度为 $n-i+1$，约束 $c_i\le n-i$ 保证所选位置存在；选完删除。生成的排列重新编码必得原向量，因为其余未选元素最终恰在右侧。反过来，原排列也会在每一步选回自己。这同时证明了编解码互逆与码的全部范围。

字典序编号要数此前的排列。首次与 $\pi$ 不同的位置若是 $i$，可在该位改选 $c_i$ 个较小未用元素，其余位置有 $(n-i)!$ 个任意完成。不同的首次差异位置互斥，所以总和就是 rank 公式。阶乘理路阶乘Factorial前 n 个正整数的乘积 n!，并约定 0!=1。在这里数自由后缀，而非某种近似权重。

取 $\pi =3142$。第一项三的右侧有一、二两个较小元素，第二项一没有，第三项四的右侧有二一个，所以

从编号十三解码：$13=2\cdot 6+1$，第一码为二，剩余一；$1=0\cdot 2+1$，第二码为零；$1=1\cdot 1+0$，第三码为一；最后码零。未用列表的选择是

恰恢复 $3142$。编号十二对应 $3124$，编号十四对应 $3214$，可直接比较邻项字典序作独立检查。

逆序总数 $\mathrm{inv}(\pi )=\sum _i{c}_i$，本例为三；它只保留各位总和，不能恢复排列。$132$ 与 $213$ 都只有一个逆序，但码分别为 $(0,1,0)$ 和 $(1,0,0)$，编号也不同。

输入 $(0,2,0)$ 不是三元素排列的合法码，因为第二位最多为一。编号 $n!$ 也超出范围，不能“取模继续”而静默改变用户指定的对象。空排列具有空码和编号零，符合 $0!=1$。

若元素有重复，剩余后缀不再有统一的 $(n-i)!$ 个不同排列，字典序排名必须按实际重数计算多项式系数；本算法不能直接对重复数据应用。一般互异标签只要先明确一个全序并映射为秩即可。

直接扫描剩余列表可在 $O(n^2)$ 次比较/移动内编码或解码，存储 $O(n)$；使用支持顺序统计的数据结构可加速，但正确性仍来自上面的剩余元素不变量。精确编号需要能容纳 $n!$ 的整数，固定字长溢出会使算法失去双射性。

各个码位独立取遍 $0,\dots ,n-i$，所以按逆序数统计的有限生成多项式理路普通生成函数Ordinary generating function把序列编码为形式幂级数 Σ a_n x^n。是

$n=4$ 时系数 $1,3,5,6,5,3,1$。这个乘积及四阶频数在既有Kendall τ 页理路Kendall τ 秩相关Kendall tau · Concordance rank correlation以两个独立观测对之间的同向和反向排序概率定义秩关联，并用随机排列推导独立原假设下的精确分布和方差。已用逐次插入推导；此处复用作为码位求和的交叉检查，新接口是确定性编解码与字典序编号。

令 $q=-1$ 可见 $n\ge 2$ 时偶逆序与奇逆序排列一样多；亦可交换两个固定位置构造反号配对。令 $q=1$ 必须用多项式形式得到 $n!$，若先写成 $(1-q^j)/(1-q)$ 再直接代一，会制造可去的零分母。

主指标等分布理路主指标与逆序数的构造性等分布Major index equidistribution · Foata second fundamental transformation · Mahonian statistics · Foata 第二基本变换以逐字分块旋转及显式逆操作证明主指标等于像的逆序数，处理重复符号，并证明逆下降集合保持。通过 Foata 第二变换把下降位置之和送成像的逆序数，因此也具有本页的 $q$ 阶乘分布。但主指标不是本页 Lehmer 码的逐位数据，不能据它独自恢复原排列。含重复符号的精细权重由Gaussian 多项式理路Gaussian 二项式与多重集加权计数Gaussian binomial coefficient · q-binomial coefficient · q-multinomial coefficient · Gaussian polynomial以二元词逆序和矩形内分拆定义q二项式，证明递推、乘积及有限q二项式定理，再推导重复字母的逆序多项式。处理；那里的 $q$ 多项式系数是逆序加权的分解结果，不能逐项把此处频数除以普通重数阶乘。