BuringStraw

作用#

求一个排列结果是在全排列中的第几项

推导#

先照搬 PPT 里的过程。

举例：对于集合{1,2,3}，求{3,2,1}是全排列中的第几项？

那么，{3,2,1}之前的有三种情况：

1. 第一项 < 3：

   一定在{3,2,1}前，此时第一项有两种选择，后两位随意，则共有

   种

2. 第一项 = 3：

   则第二项 < 2 时结果小于{3,2,1}

3. 前两项相等：

   没有比{3,2,1}小的

总共2*2!+1*1!+0=5种

计算公式#

其中 pi 表示在没选中的元素中比 ai 小的的数量

逆推#

给定一个序号，求出排列结果。

例：对于集合{1,2,3,4,5,6}，求出全排列的第 100 项（从 0 开始计数）。

这个。。。直接上张 ppt 吧。