目录

• 什么是分治法？
• 分析什么是全排列
• 代码（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,2)
		=========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