目录

• 什么是分治法？

• 分析什么是全排列

• 代码（c++）

• java实现

• 递归结构展示

什么是分治法？

先看分：将一个大问题分成若干个小问题，如果小问题还可以分，那就再分，直到小问题可以很轻易地解决

治：将小问题逐个解决，然后将解合起来，组成大问题的解。

下图是示意图：

image

分析什么是全排列

目的是对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)这个大问题，我们可以最终分解为：（下图列出了固定第一个元素的情况）

image

代码（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