通过swap方式生成的全排列并不是字典顺序的：

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int A[20];int cnt;int recur;void perm(int cur, int n, int *A){    recur++;    if(cur==n)//empty    {        cnt++;        for(int i=0;i
          
           >n; for(int i=0;i
          
         
        
       
      
     

上面代码n=3时，输出如下：

1 2 3

1 3 2

2 1 3

2 3 1

3 2 1

3 1 2

6

16

可以看出叶子节点数目为6，需要递归16次（即所有的节点数目）

第一层cur 0

第二层cur 1

第n+1层cur n  都是叶节点。

但是要注意，3开头的就不是字典顺序了。

 

按顺序填充遍历方式能保证字典顺序；

#include
     
      #include
      
       #include
       
        using namespace std;int n, A[50], isp[50], vis[50];int cnt;int recur;void dfs(int cur) {    recur++;  if(cur == n ) {      cnt++;    for(int i = 0; i < n; i++) printf("%d ", A[i]);    printf("\n");  }  else for(int i = 1; i <= n; i++)    if(!vis[i]) {      A[cur] = i;      vis[i] = 1;      dfs(cur+1);      vis[i] = 0;    }}int main() {  scanf("%d", &n);  memset(vis, 0, sizeof(vis));  dfs(0);  printf("%d\n", cnt);  printf("%d\n", recur);  return 0;}
       
      
     

输出结果：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

6

16

可以看出树的节点数和上面的算法是一样的，所以效率是差不多的。但是这个算法却可以保证字典顺序生成排列。