含分隔符的递增排列Rank与Unrank：计数及高效实现方案问询

1. 有效排列总数计算 #

给定n个排列元素（1~n）和b个分隔符（0），要求任意两个分隔符之间的元素保持递增。这类有效排列的总数为 (b+1)^n。

原理 #

每个元素可以独立选择进入b+1个“区间”中的任意一个（b个分隔符将序列划分为b+1个有序区间：分隔符前、分隔符之间、分隔符后）。每个区间内的元素自动按递增顺序排列，因此每个元素的区间选择对应唯一的有效排列，反之亦然。总共有(b+1)种选择给每个元素，n个元素的总组合数就是(b+1)的n次方。

2. Rank与Unrank实现 #

Rank操作（给定有效序列，计算其排名） #

排名指该序列在所有有效序列字典序中的索引（从0开始）。计算步骤如下：

1. 初始化rank=0，used为空集合（记录已出现的元素），placed_barriers=0（已放置的分隔符数量）。
2. 从左到右遍历序列的每个元素：
   • 当前元素是分隔符0：
     若还能放置分隔符（placed_barriers < b），由于0是最小的字符，没有比它更小的合法字符，直接更新placed_barriers +=1即可。
   • 当前元素是元素x：
     首先，若还能放置分隔符，计算“当前位置放0时后续的有效序列数”：count = (b - placed_barriers) ** (n - len(used))，将该数累加到rank（因为放0的序列比当前序列小）。
     然后，遍历所有未使用且小于x的元素y：
     计算“当前位置放y时后续的有效序列数”：count = ((b+1) - placed_barriers) ** (n - len(used) -1)，将该数累加到rank。
     最后，将x加入used集合。
3. 遍历结束后，rank即为该序列的排名。

Unrank操作（给定排名，生成对应有效序列） #

通过反向推导构造序列，步骤如下：

1. 初始化remaining_rank=rank，used为空集合，placed_barriers=0，result为空列表。
2. 循环构造序列直到长度为n+b：
   • 尝试放置分隔符0：
     若还能放置分隔符，计算“放0后后续的有效序列数”：count = (b - placed_barriers) ** (n - len(used))。
     若remaining_rank < count，说明当前位置应放0，将0加入result，更新placed_barriers +=1，进入下一轮循环。
     否则，将remaining_rank -= count，继续尝试放置元素。
   • 尝试放置元素：
     从小到大遍历未使用的元素y：
     计算“放y后后续的有效序列数”：count = ((b+1) - placed_barriers) ** (n - len(used) -1)。
     若remaining_rank < count，说明当前位置应放y，将y加入result，更新used.add(y)，进入下一轮循环。
     否则，将remaining_rank -= count，继续遍历下一个元素。

关键计算说明 #

• 放分隔符后的后续序列数：放置当前分隔符后，剩余元素只能分配到剩下的b - placed_barriers个区间，因此数量为(b - placed_barriers)^剩余元素数。
• 放元素后的后续序列数：放置当前元素后，剩余元素可分配到当前区间及后续所有区间（共(b+1) - placed_barriers个），因此数量为((b+1)-placed_barriers)^剩余元素数。

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