求排列：swap交换法

核心：

分治+回溯

1. dfs(s,t)表示：本轮要放的位置是s，待排列的区间是[s,t]
2. 对于当前位置s，尝试将[s,t]内的每个元素放到s一次
3. swap(a[s],a[i])：
   (1) a[s]->a[i]将a[s]这个数扔到待排序部分
   (2) a[s]<-a[i]将a[i]这个数放到位置s上
4. dfs(s+1,t)：放第s+1个位置
5. swap(a[s],a[i])：回溯
6. 同一层dfs(s,t)：遍历每一种可能——尝试在位置s放不同的数

模版：

void dfs(int s,int t)//正在放位置为s的数 
{if(s==t){//若[s,t]只有一个数 a[s]原地不动 for(int i=startIndx;i<=t;++i) cout<<a[i];cout<<"\n";}for(int i=s;i<=t;++i){swap(a[s],a[i]);//位置s放数a[i] dfs(s+1,t);//放位置s+1 swap(a[s],a[i]);//换回来 }
}

例子：

假设数组是[1,2,3]，要得到这三个数的全排列

dfs(0,2):当前要放第0个位置的数
|---i=0: swap(a[0],a[0]) -> [1,2,3] 第0个位置放a[0]
|        dfs(1,2):当前要放第1个位置的数
|		 |--i=1: swap(a[1],a[1]) -> [1,2,3] 第1个位置放a[1]
|		 |		 dfs(2,2):		cout<<[1,2,3]
|		 |		 swap(a[1],a[1]) -> [1,2,3] 换回来(回溯)
|		 |--i=2: swap(a[1],a[2]) -> [1,3,2] 第1个位置放a[2]
|		 |		 dfs(2,2):		cout<<[1,3,2]
|		 |		 swap(a[1],a[2]) -> [1,2,3] 换回来(回溯)
|		 swap(a[0],a[0]) -> [1,2,3]
|
|---i=1: swap(a[0],a[1]) -> [2,1,3] 第0个位置放a[1]
|        dfs(1,2):当前要放第1个位置的数
|		 |--i=1: swap(a[1],a[1]) -> [2,1,3]
|		 |		 dfs(2,2):		cout<<[2,1,3]
|		 |		 swap(a[1],a[1]) -> [2,1,3]
|		 |--i=2: swap(a[1],a[2]) -> [2,3,1]
|		 |		 dfs(2,2):		cout<<[2,3,1]
|		 |		 swap(a[1],a[2]) -> [2,1,3]
|		 swap(a[0],a[1]) -> [1,2,3]
|
|---i=2: swap(a[0],a[2]) -> [3,2,1] 第0个位置放a[2]dfs(1,2):当前要放第1个位置的数|--i=1: swap(a[1],a[1]) -> [3,2,1] |		 dfs(2,2):		cout<<[3,2,1] |		 swap(a[1],a[1]) -> [3,2,1] |--i=2: swap(a[1],a[2]) -> [3,1,2]|		 dfs(2,2):		cout<<[3,1,2]|		 swap(a[1],a[2]) -> [3,2,1]swap(a[0],a[2]) -> [1,2,3]

变式：

求数组某段区间的全排列，类似于求\((A^k_n)\)

int a[]={1,7,3,2};
int startIndx,endIndx;void dfs(int s,int t)//正在放位置为s的数 
{if(s==t){//若[s,t]只有一个数 a[s]原地不动 for(int i=startIndx;i<=t;++i) cout<<a[i];cout<<"\n";}for(int i=s;i<=t;++i){swap(a[s],a[i]);//位置s放数a[i] dfs(s+1,t);//放位置s+1 swap(a[s],a[i]);//换回来 }
}int main()
{startIndx=1,endIndx=3;dfs(startIndx,endIndx); return 0;
}