递归方式-全排列生成算法

偏执的太偏执、 2022-10-19 04:25 206阅读 0赞

[http://blog.csdn.net/xiazdong/article/details/7986015][http_blog.csdn.net_xiazdong_article_details_7986015]

排列：从n个元素中任取m个元素，并按照一定的顺序进行排列，称为排列；

全排列：当n==m时，称为全排列；

比如：集合\{ 1,2,3\}的全排列为：

\{ 1 2 3\}

\{ 1 3 2 \}

\{ 2 1 3 \}

\{ 2 3 1 \}

\{ 3 2 1 \}

\{ 3 1 2 \}

方法一：

我们可以将这个排列问题画成图形表示，即排列枚举树，比如下图为\{1,2,3\}的排列枚举树，此树和我们这里介绍的算法完全一致；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FwcGxleXVjaGk_size_16_color_FFFFFF_t_70][]

算法思路：

(1)n个元素的全排列=（n-1个元素的全排列）+（另一个元素作为前缀）；

(2)出口：如果只有一个元素的全排列，则说明已经排完，则输出数组；

(3)不断将每个元素放作第一个元素，然后将这个元素作为前缀，并将其余元素继续全排列，等到出口，出口出去后还需要还原数组；

\[java\] [view plain][] [copy][view plain]

1.  public class Test \{  
2.      public static int arr\[\] = new int\[\]\{1,2,3\};  
3.      public static void main(String\[\] args) \{  
4.          perm(arr,0,arr.length-1);  
5.      \}  
6.      private static void swap(int i1, int i2) \{  
7.          int temp = arr\[i2\];  
8.          arr\[i2\] = arr\[i1\];  
9.          arr\[i1\] = temp;  
10.     \}  
11.   
12.     /\*\* 
13.      \* 对arr数组中的begin~end进行全排列 
14.      \*  
15.      \* 比如： 
16.      \*  arr = \{1,2,3\} 
17.      \*  第一步：执行 perm(\{1,2,3\},0,2),begin=0,end=2; 
18.      \*      j=0,因此执行perm(\{1,2,3\},1,2),begin=1,end=2; 
19.      \*          j=1,swap(arr,0,0)-->arr=\{1,2,3\},  perm(\{1,2,3\},2,2),begin=2,end=2; 
20.      \*              因为begin==end，因此输出数组\{1,2,3\} 
21.      \*          swap(arr,1,1) --> arr=\{1,2,3\}; 
22.      \*          j=2,swap(arr,1,2)-->arr=\{1,3,2\},  perm(\{1,3,2\},2,2),begin=2,end=2; 
23.      \*              因为begin==end，因此输出数组\{1,3,2\} 
24.      \*          swap(arr,2,1) --> arr=\{1,2,3\}; 
25.      \*      j=1,swap(arr,0,1) --> arr=\{2,1,3\},     perm(\{2,1,3\},1,2),begin=1,end=2; 
26.      \*          j=1,swap(arr,1,1)-->arr=\{2,1,3\}   perm(\{2,1,3\},2,2),begin=2,end=2; 
27.      \*              因为begin==end，因此输出数组\{2,1,3\} 
28.      \*          swap(arr,1,1)--> arr=\{2,1,3\}; 
29.      \*          j=2,swap(arr,1,2)后 arr=\{2,3,1\},并执行perm(\{2,3,1\},2,2),begin=2,end=2; 
30.      \*              因为begin==end，因此输出数组\{2,3,1\} 
31.      \*          swap(arr,2,1) --> arr=\{2,1,3\}; 
32.      \*      swap(arr,1,0)  --> arr=\{1,2,3\} 
33.      \*      j=2,swap(arr,2,0) --> arr=\{3,2,1\},执行perm(\{3,2,1\},1,2),begin=1,end=2; 
34.      \*          j=1,swap(arr,1,1) --> arr=\{3,2,1\} , perm(\{3,2,1\},2,2),begin=2,end=2; 
35.      \*              因为begin==end，因此输出数组\{3,2,1\} 
36.      \*          swap(arr,1,1) --> arr=\{3,2,1\}; 
37.      \*          j=2,swap(arr,2,1) --> arr=\{3,1,2\},并执行perm(\{2,3,1\},2,2),begin=2,end=2; 
38.      \*              因为begin==end，因此输出数组\{3,1,2\} 
39.      \*          swap(arr,2,1) --> arr=\{3,2,1\}; 
40.      \*      swap(arr,0,2) --> arr=\{1,2,3\} 
41.      \*       
42.      \* @param arr 
43.      \* @param begin  
44.      \* @param end 
45.      \*/  
46.     public static void perm(int arr\[\], int begin,int end) \{  
47.         if(end==begin)\{         //一到递归的出口就输出数组，此数组为全排列  
48.             for(int i=0;i<=end;i++)\{  
49.                 System.out.print(arr\[i\]+" ");  
50.             \}  
51.             System.out.println();  
52.             return;  
53.         \}  
54.         else\{  
55.             for(int j=begin;j<=end;j++)\{   
56.                 swap(begin,j);      //for循环将begin~end中的每个数放到begin位置中去  
57.                 perm(arr,begin+1,end);  //假设begin位置确定，那么对begin+1~end中的数继续递归  
58.                 swap(begin,j);      //换过去后再还原  
59.             \}  
60.         \}  
61.     \}  
62. \}

方法二：

![20210709151211200.gif][]

\[java\] [view plain][] [copy][view plain]

1.  public class Test2 \{  
2.      public static int arr\[\] = new int\[\]\{0,0,0\};  
3.      public static void main(String\[\] args) \{  
4.          perm(3);  
5.      \}  
6.      /\*\* 
7.       \* 数组变化过程： 
8.       \* 3 0 0 
9.       \* 3 2 0 
10.      \* 3 2 1 
11.      \* 3 2 0 
12.      \* 3 0 0 
13.      \* 3 0 2 
14.      \* 3 1 2 
15.      \* 3 0 2 
16.      \* 3 0 0 
17.      \* 0 0 0 
18.      \* 0 3 0 
19.      \* 2 3 0 
20.      \* 2 3 1 
21.      \* 2 3 0 
22.      \* 0 3 0 
23.      \* 0 3 2 
24.      \* 1 3 2 
25.      \* 0 3 2 
26.      \* 0 3 0 
27.      \* 0 0 0 
28.      \* 0 0 3 
29.      \* 2 0 3 
30.      \* 2 1 3 
31.      \* 2 0 3 
32.      \* 0 0 3 
33.      \* 0 2 3 
34.      \* 1 2 3 
35.      \* 0 2 3 
36.      \* 0 0 3 
37.      \* 0 0 0 
38.      \* @param m 
39.      \*/  
40.     private static void perm(int m) \{  
41.         if(m==0)\{  
42.             for(int i=0;i<arr.length;i++)\{  
43.                 System.out.print(arr\[i\]+" ");  
44.             \}  
45.             System.out.println();  
46.             return;  
47.         \}  
48.         else\{  
49.             for(int i=0;i<arr.length;i++)\{  
50.                 if(arr\[i\]==0)\{  
51.                     arr\[i\] = m;  
52.                     perm(m-1);  
53.                     arr\[i\] = 0;  
54.                 \}  
55.             \}  
56.         \}  
57.     \}  
58. \}

参考文献：

1.全排列的递归算法实现   李盘荣

2.全排列递归算法在算法教学中的重要性  吴素萍

3.排序算法与全排列生成算法研究 陈卫东, 鲍苏苏

论文下载地址：http://yunpan.cn/lk/05qsom5mle

Reference:

[递归解决全排列生成算法\_xiazdong-CSDN博客\_全排列递归][xiazdong-CSDN]

[http_blog.csdn.net_xiazdong_article_details_7986015]: http://blog.csdn.net/xiazdong/article/details/7986015
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FwcGxleXVjaGk_size_16_color_FFFFFF_t_70]: /images/20221005/002fe723cf2a47898aca1b627ed306bb.png
[view plain]: http://blog.csdn.net/xiazdong/article/details/7986015#
[20210709151211200.gif]: /images/20221005/bd64313acc91436a90f295520733f89e.png
[xiazdong-CSDN]: https://blog.csdn.net/xiazdong/article/details/7986015