全排列
顾名思义：就是将所有元素按照一定顺序排列一遍。
例如：现在有一组数组[1,2,3]
这个数组全排列的结果就是 { [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] }
这么说就懂了吧！
那么如何用 编程 解决呢？
说到排列，那么最常用的自然是递归！
那么问题又来了，怎么 “递”？
咱先来个思维导图（以下图中的数组为例）
一般对某一个数组进行排列的顺序是从后往前，将前面的部分固定，对后面的序列子集进行排列。
此时就需要划分 一条 分割线，说是一条，实际上每个元素的左侧都有一条分割线，但这条“分割线”只能向右移动，移动到最右侧后失效。
最外层分割线的划分是从右往左的，当划分了最外层分割先后，右侧的分割线均视为子集分割线。
如下图：
第一次排列：即按字典序（由小到大）排列。第一次可排列的最外层分割线为3，4之间。
也就是所谓的”退格“，每退一格，就从队列里删除一位。
同时用一个高级的玩意儿——布尔值数组，将外层分割线以右对应的布尔数组位设置为 false。
这一操作叫做 回溯 ，此时外层分割线右侧的分割线均为子集分割线，首先是第一个子集分割线向右移动，每遇到一个 false 就将该布尔数组对应的数字推入队列。
例如，上一次排列为：1，2，3，4，5
此时最外层分割线在3 4 之间，那么子集分割线初始化在4 5之间，向右移动的第一个遇到的第一个false是5，那么就将5推入队列，5入列后子集分割线的任务也完成了；
此时回溯的作用就出来了，最外层分割线开始往右移动，遇到了为false的4，然后将4推入队列。
此时队列数据为：1，2，3，5，4
true1 true2表示的是顺序，例如这里5先变true，那么5就比4早入队。（队列和布尔数组不是一一对应的，队列里的数字才是和布尔数组对应的）。
同理：在最外层分割线也移动到最右侧后，就失效了，此时的最外层分割线就变到了2，3之间，3，4之间的分割线变成了第一层子集分割线。按照上面的逻辑开始这一层的排列。
理解了这些，就可以开始编写代码了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class S_Num{
int n; //元素的总数
List<Integer> list = new ArrayList<>();//当前正在排列的顺序
boolean[] visited; //***重点*** 通过这个布尔值来控制队列中的值
public S_Num(int n){
this.n = n;
visited = new boolean[n+1];//最好+1
}
/**
* @param step 步骤：也就是每一层分割线分割的部分所排列的过程。
*/
public void fullAlignment(int step){
//判断此部分（分割线划分部分）是否完成排列。
if(step>n){
for(int i = 0;i<list.size;i++){
System.out.println(list.get(i));
}
return;
}
for(int i = 1;i<=n;i++){
//每一层分割线的判断
if(!visited[i]){
visited[i] = true;
list.add(i);
//开始递归
fullAlignment(step+1);
visited[i] = false;//回溯
list.remove(i);
}
}
}
}