先用一个例子简单介绍一下这个原理
12345找出这个序列全排列的第16个
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiclRnblN0LclHdpZXYyd2LcBzNvwVZ2x2bzNXak9CX90TQNNkRrFlQKBTSvwFbslmZvwFMwQzLcVmepNHdu9mZvwFVywUNMZTY18CX052bm9CX9MmaOJTTq1UMZpXTmZEWjZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39zN4QTN0czMzIDOyETM3EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
计算方法就是如果你要求12345全排列的第16个的话
求第一位 用15/4!=0余15,那么前面有0个数,得到1。那么此时12345剩下了2345。
求第二位 用余的15/3! = 2余3,那么前面有2个数,得到4。剩下235。
求第三位 用余的3/2! = 1余1,那么前面有1个数,得到3,剩下25。
求第四位 用余的1/1! = 1余0,那么前面有1个数,得到5,剩下2。
求第五位 即2。
为什么可以这样求?下面是原理分析。
这里我们列出了分别由1,2,3,4,5开头的数分布在哪些区间。如1开头的数,就分布在1到4!。2开头的数,就分布在4!+1到2*4!。。。
再细化一下,这里又列出了21,22,23,24开头的4个数。21是4!+1到4!+3!。22是4!+1+3!到4!+2*3!。。。
所以我们不难得知,我们这样在求余数的过程中,其实就是在给这些数在定位。
我们求15/4!=0余15。那么就意味着我们第一个数是在第一个区间,即1.
这里我们余得15,就是我们在这个区间内的第15个数。
15/3!=2余3。那么我们第二个数就是剩下的2345的第三个数(因为余数是从0开始的)。以此类推。
为什么我们求16又用的是15而不是16呢?那你用1带进去试试看。最后除出来的结果是1/1!=1余0.所以是在第二个区间那就是2?当然不对。
我们这里减一位开始是为了考虑余数是从0开始为我们定位这个区间的。
换个问法,14352是第几个数?当然用上面例子的反向思维!如果领悟了上面的图,这里会不假思索地写出答案:16。嘿嘿。