目录
什么是分治法？
分析什么是全排列
代码（c++）
java实现
递归结构展示
什么是分治法？
先看分：将一个大问题分成若干个小问题，如果小问题还可以分，那就再分，直到小问题可以很轻易地解决
治：将小问题逐个解决，然后将解合起来，组成大问题的解。
下图是示意图：
分析什么是全排列
目的是对n不重复的字符{a1,a2,a3....an}进行全排列， 以n=4时为例，对{a,b,c,d}全排列可以写为
P(a,b,c,d)={a}P(b,c,d)+ {b}P(a,c,d) + {c}P(a,b,d) +{d}P(a,b,c);
即四个元素的全排列为下面四种情况相加：
(1)把第一个元素固定住，剩下的全排列{a}P(b,c,d)
(2)把第二个元素固定住，剩下的全排列 {b}P(a,c,d)
(3)把第三个元素固定住，剩下的全排列{c}P(a,b,d)
(4)把第四个元素固定住，剩下的全排列{d}P(a,b,c)
也就是说，对n个元素的全排列是
a1和其余n-1个元素全排列的组合
a2和其余n-1个元素全排列的组合
+....+
an和其余n-1个元素全排列的组合
记作
P(a1,a2....an)={a1}P(a2....an)+ {a2}P(a1,a3,a4.....an) + {a3}P(a1,a2,a4.....an) +{an}P(a1.....a(n-1));
同样的，对于上面粗体的P(a2....an)，我们同样可以分解为更小的组合：
P(a2....an)= {a2}P(a3....an)+ {a3}P(a2,a4.....an) + {a4}P(a2,a3.....an) +{an}P(a2.....a(n-1));
如此往复一直分，直到什么情况为止呢？上面我们说了，分解子问题直到子问题可以很轻易地解决，那什么情况时全排列很容易解决呢？
我们发现当n=1时，P(a1)为{a1}，即只有一个元素时，它的全排列就是它本身, 所以当要排列的元素个数为1时，我们可以直接得出结果，那就是前面元素加上它本身就是一种排列的情况。
如当n=2时，P(a1,a2)分解成{a1}P(a2)+ {a2}P(a1), 而P(a2)=a2, P(a1)=a1,所以结果为P(a1,a2)为{a1,a2}{a2,a1}
故对P(a,b,c,d)这个大问题，我们可以最终分解为：（下图列出了固定第一个元素的情况）
代码（c++）
#include "stdlib.h"
#include "stdio.h"
template<class Type>
inline void swap(Type &a,Type &b,Type lt[]) {
Type t = a; a = b; b = t;
}
template<class Type>
inline void printList(Type lt[]) {
printf("==>%s\n\n",lt);
}
template<class Type>
void perm(Type list[], int k,int m) {
if(k==m) {
swap(list[k],list[k],list);
printList(list);
}
else {
for(int i=k;i<=m;i++) {
swap(list[k],list[i],list);
perm(list,k+1,m);
swap(list[k],list[i],list);
}
}
}
int main(int argc, char* argv[]) {
char ll[] = "abcd";
perm(ll,0,3);
system("pause");
return 0;
}
java实现
摘自zyoung贡献
public class Demo {
public void Perm(char list[], int k, int m) {
if (k == m) {
for (int i = 0; i <= m; i++)
System.out.print(list[i]);
System.out.println();
} else {
for (int i = k; i <= m; i++) {
// 从固定的数后第一个依次交换
Swap(list, k, i);
Perm(list, k + 1, m);
// 这组递归完成之后需要交换回来
Swap(list, k, i);
}
}
}
public void Swap(char[] list, int i, int j) {
char t = list[i];
list[i] = list[j];
list[j] = t;
}
public static void main(String[] args) {
Demo d = new Demo();
char[] arr = {a,b,c,d};
d.Perm(arr, 0, 3);
}
}
递归结构展示
输入：Perm(list, 0, 3 )
=====i=k=0,i<=3(第一个为a)
Swap(0,0)abcd
Perm(list,1,3)
=========i=k=1,i<=3
Swap(list , 1, 1)abcd
Perm(list, 2, 3)
======i=k=2, i<=3
Swap(2,2)abcd
Perm(list, 3,3)
Print(list)abcd
Swap(list,2,2)
=====i=i+1,i=3
Swap(2,3)abdc
Perm(list, 3,3)
Print(list)abdc
Swap(list,2,3)abcd
======out
Swap(list,1,1)abcd
========i=i+1, i=2<3,k=1
Swap(list , 1, 2)acbd
Perm(list, 2, 3)
======i=k=2, i<=3
Swap(2,2)acbd
Perm(list, 3,3)
Print(list)acbd
Swap(list,2,2)acbd
=====i=i+1,i=3
Swap(list,2,3)acdb
Perm(list, 3,3)
Print(list)acdb
Swap(list,2,3)acbd
======out
Swap(list,1,2)abcd
========i=i+1, i=3,k=1
Swap(list , 1, 3)adcb
Perm(list, 2, 3)
======i=k=2, i<=3
Swap(2,2)adcb
Perm(list, 3,3)
Print(list)adcb
Swap(list,2,2)adcb
=====i=i+1,i=3
Swap(list,2,3)adbc
Perm(list, 3,3)
Print(list)adbc
Swap(list,2,3)adcb
======out
Swap(list,1,3)abcd
=========out
Swap(0,0)abcd
=====i=i+1,i=1,i<=3,k=0(第一个为b)
Swap(0,1)bacd
Perm(list,1,3)
=========i=k=1,i<=3
Swap(list , 1, 1)bacd
Perm(list, 2, 3)
======i=k=2, i<=3
Swap(2,2)bacd
Perm(list, 3,3)
Print(list)bacd
Swap(list,2,2)
=====i=i+1,i=3
Swap(2,3)badc
Perm(list, 3,3)
Print(list)badc
Swap(list,2,3)bacd
======out
Swap(list,1,1)bacd
========i=i+1, i=2<3,k=1
以此类推
out
==>abcd
==>abdc
==>acbd
==>acdb
==>adcb
==>adbc
==>bacd
==>badc
==>bcad
==>bcda
==>bdca
==>bdac
==>cbad
==>cbda
==>cabd
==>cadb
==>cdab
==>cdba
==>dbca
==>dbac
==>dcba
==>dcab
==>dacb
==>dabc
该文章同步发表于csdn
