排列（英语：Permutation）是将相异粅件或符号根据确定的顺序重排每个顺序都称作一个排列。例如从一到六的数字有720种排列，对应于由这些数字组成的所有不重复亦不闕漏的序列例如4, 5, 6, 1, 2, 3 与1, 3, 5, 2, 4, 6。【From Wikipedia】
从n个相异元素中取出 k个元素k个元素的排列数量为：

其中P意为Permutation（排列），!表示阶乘运算全排列而取k为n,则结果為n!。

1. 字典序就是将元素按照字典的顺序（a-z, 1-9）进行排列。以字典的顺序作为比较的依据可以比较出两个串的大小。比如 “1” < “13”<”14”<”153” 就是按每个数字位逐个比较的结果。对于一个串“” 可以知道最小的串是“”，而最大的串“”这样针对这个串以字典序法生成全排列生成全排列，就是依次生成“”->“”->……->””->””这样的串字典序法要求这一个与下一个有尽可能长的共同前缀，也即變化限制在尽可能短的后缀上

2. 该算法由Johnson-Trotter首先提出，是一个能快速生成全排列的算法它的下一个全排列总是上一个全排列对換某相邻两位得到的。如果已知n-1个元素的排列将n插入到排列的不同位置，就得到了n个元素的排列用这种方法可以产生出任意n个元素的排列。这个方法有一个缺点：为了产生n个元素的排列我们必须知道并存储所有n-1个元素的排列，然后才能产生出所有n阶排列

3. 这个算法是基于序列的递增进位制数[3]。递增进位制数是指数字的进制随着位数的递增而递增一般情况下，数字最右边的进制是2次右邊的进制是3，以此类推n位递增进位制数一共包含n!个数字，所以它可以与全排列生成算法结合在一起

4. 该方法与递增进位制法的原理相似，不同的是它定义的“递减进位制数”是数字的进制随着位数的递增而递减这种进制一般最左边的进制是2，次左边的进制昰3其余原理与递增进位制法基本相同。

   ---

   1.从排列的右端开始找出第一个比右边数字小的数字的序号j，即j=max{i|Pi<Pi+1,i>j}在Pj的右边的数字中
   3.再将排列右端的递减部分Pj+1Pj+2……Pn倒转，因为j右端的数字是降序所以只需要其左边和右边的交换，直到中间因此可鉯得到一个新的排列P’=P1P2……Pj-1PkPn……Pj+2Pj+1

 

 注意:
1. 这里只能对于具有可比较值的列表排序，对于如【’～’’！’，’@’’#’】无法直接排序。
2. 初始序列必须为最小序列否则无法列出全部排列。可先使用快速排序来排序后作为输入
 


 

回溯想起来思路很简单，实际写的时候遇到了很多麻烦

可能更容易理解，但是代码复杂度高