排列的生成(一) —— 字典序法

1.定义

  在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。 这种泛化主要在于定义有序完全有序集合（通常称为字母表）的元素的序列（通常称为计算机科学中的单词）的总顺序。
  对于数字1、2、3…n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。 [百度百科]

2.字典序算法

设$P$P是1~n的一个全排列：$P=p_1p_2\dots p_n$P=p1​p2​…pn​。则在字典序中，求这个数的下一个排列是多少？
（1）从右到左找最长的降序子列$p_{i+1}\dots p_n$pi+1​…pn​，记下$p_i$pi​。
（2）在序列中找比$p_i$pi​大的最右边一位$p_k$pk​，交换$p_i$pi​和$p_k$pk​。
（3）将$p_k$pk​右侧子列倒排。

• 例子1
  
• 例子2
  
• 例子3
  

3.问题一：问一个数属于字典序中的第几个排列？

一个排列$p_1p_2p_3\dots p_n$p1​p2​p3​…pn​对应一个’序数’：$a_1a_2\dots a_{n-1}$a1​a2​…an−1​。
$a_i$ai​代表$p_i$pi​的右边比$p_i$pi​小的数字的个数。则在字典序中，排序$p_1p_2p_3\dots p_n$p1​p2​p3​…pn​的位次排名为：
$d = a_1(n-1)!+a_2(n-2)!+a_3(n-3)!+\dots+a_{n-2}2!+a_{n-1}1!$d=a1​(n−1)!+a2​(n−2)!+a3​(n−3)!+⋯+an−2​2!+an−1​1!
注意：$d=0,1,2,\dots,n!-1$d=0,1,2,…,n!−1

4.问题二：问字典序中的第几个排列是多少？

假设一个字典序排列由1到4组成，问第21个排列是多少？(排名从0开始数，当然也可以从1开始)
该字典排列总共有$n!=4!=24$n!=4!=24种。
（1）先固定第一位数为1，它在字典序中的最小排名为$0 \times 3! + 0 \times 2! + 0 \times 1!=0$0×3!+0×2!+0×1!=0，即1234。
它在字典序中的最大排名为$0 \times 3! + 2 \times 2! + 1 \times 1!=5$0×3!+2×2!+1×1!=5。所以第一位为1的排列是不行的。由此进行下去，我们发现第一位为4时，它在字典序中的最小排名为$3 \times 3! + 0 \times 2! + 0 \times 2! + 0 \times 1! = 18$3×3!+0×2!+0×2!+0×1!=18，在字典序中最大的排名为$3 \times 3! + 2 \times 2! + 1 \times 1!=23$3×3!+2×2!+1×1!=23。因此该排列的第一位数为4。
（2）先固定第2位数为1。则它在字典序中对应的最小排名为$3 \times 3! + 0 \times 2! + 0 \times 1!= 18$3×3!+0×2!+0×1!=18，在字典序中的最大排名为$3 \times 3! + 0 \times 2! + 1 \times 1!=19$3×3!+0×2!+1×1!=19。依次往下找，我们发现第2位为2时，对应的最小排名为$3 \times 3! + 1 \times 2! + 0 \times 1!= 20$3×3!+1×2!+0×1!=20，在字典序中的最大排名为$3 \times 3! + 1 \times 2! + 1 \times 1!=21$3×3!+1×2!+1×1!=21。刚好是我们想要的。因此该排列的第一位为4，第二位为2，同时还得满足这两位固定后的最大排名，即这个数为4231。

参考博客
https://www.cnblogs.com/darklights/p/5285598.html
https://blog.****.net/cpfeed/article/details/7376132