递归详解,全排列问题

递归 Recursion

关键词: 递归树(recursion tree) 

全排列问题

问题描述:

用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列, 
如 abc 的全排列: abc, acb, bca, dac, cab, cba

thinking path:

进行全排列,对每种可能进行枚举,例如123,那么可以1与2互换,1与3互换,以及2与3互换。

问题稍微扩展为1234,1分别与2,3,4互换。总结规律就是对某个数,与其后面的数一一进行互换,得出该数在该位置的所有可能。

将该数向后“递进”一个位置,例如,1234,1与2互换后为,2134,再用同样的方法尝试2134中1后面的所有能与1互换的数字。

根据规律,可以列出递归伪代码:

allArrange(str,k,m) {

 if k==m print; 

 for i=k to m {

   swap(str,k,i); //k为第k个数

   allArrange(str,k+1,m);

   swap(str,k,i); //注意,因为递归有回溯的过程,所以需要把数字重新调换回来变为”初始“的排列。

 }

}

贴出完整C代码

递归详解,全排列问题
 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 void swap(char* a, char* b) {
 5  char tmp = *a;
 6  *a = *b;
 7  *b = tmp;
 8 }
 9 
10 void allArrange(char* str, int currentIndex, int m) {
11     if (currentIndex == m) {
12         static int s_i = 1;
13         printf("currentIndex is %d, m is %d\n",currentIndex, m);
14         printf("the %2dth arrangement\t%s\n",s_i++, str);
15     } else {
16         for (int i = currentIndex; i <= m; i++) {
17         
18           swap(str+currentIndex, str+i);
19           allArrange(str, currentIndex+1, m);
20           swap(str+currentIndex, str+i);
21          }
22 
23     }
24 }
25 void arrange(char* str) {
26     allArrange(str, 0, strlen(str)-1);
27 }
28 int main() {
29     char str[] = "12345";
30     arrange(str);
31     return 0;
32 }
递归详解,全排列问题

递归的过程不易理解,可以画递归树(Recursion Tree)帮助理解。以"123"为例:

递归详解,全排列问题

递归详解,全排列问题

上一篇:一个 Crash 引发的血案


下一篇:linux常用命令(自我积累)