递归详解(四)

 1 public class A {
 2     static int k=0;
 3     static int temp_k=0;
 4     static int p=0;
 5     static int q=0;
 6     public static void main(String args[]) {
 7         char[] ss = { '1', '2', '3','4','5','1', '2', '3','4','5'};
 8         permutation(ss, 0);
 9         if(temp_k == k)  {
10             System.out.println(k);
11             System.out.println(p);
12             System.out.println(q);
13         }
14     }
15     public static void permutation(char[] ss, int i) {
16         
17         if (ss == null || i < 0 || i > ss.length) {
18             return;
19         }
20         if (i == ss.length) {
21             String a = new String(ss);    
22             k++;
23             temp_k = k;
24             if(k==3628800)
25             System.out.println(a);
26         } else {
27             for (int j = i; j < ss.length; j++) {
28                 char temp = ss[j];// 交换前缀,使之产生下一个前缀
29                 ss[j] = ss[i];
30                 ss[i] = temp;
31                 p++;
32                 permutation(ss, i + 1);
33                 q++;
34                 temp = ss[j]; // 将前缀换回来,继续做上一个的前缀排列.
35                 ss[j] = ss[i];
36                 ss[i] = temp;
37             }
38         }
39     }
40 }

对10个数进行排列，k存放总排列情况的个数，p、q分别存放入栈和出栈的次数。顺便打印出最后一种排列，结果：

排列总数为10！
计算规律如下：

n	1	2	3	4	5	6	10
k	1	2	6	24	120	720	10！
p	1	4	15	64	325	1956	9864100

可见算法效率比较低，递归入栈的次数远大于全排列的次数，随着n值的增加，p/n趋近于自然对数e。