全排列

蔚落 2022-01-29 04:55 333阅读 0赞

talk is cheap, show me the code.

public static void permutation(char[]ss,int i){   
          if(ss==null||i<0 ||i>ss.length){ //1 
              return;  
          }
          
          if(i==ss.length-1){ //2 
              System.out.println(new String(ss));  
          }else{   
              for(int j=i;j<ss.length;j++){ //3 
                  char temp=ss[j];//交换前缀,使之产生下一个前缀 
                  ss[j]=ss[i];  
                  ss[i]=temp;  
                  permutation(ss,i+1);//4 
                  temp=ss[j]; //将前缀换回来,继续做上一个的前缀排列.//5 
                  ss[j]=ss[i];  
                  ss[i]=temp;  
              }   
          }  
      }  
      public static void main(String args[]){ 
      	permutation(new char[]{ 'a','b','c','d'},0);
      }

再谈理解：  
这里采用的是递归的方法实现，注释1不用多说，对要进行全排列的数据进行判空校验。

这里先看注释3，从main方法进来之后会先道注释3这部分的代码，此时i=0，j=0,（数组内元素\{‘a’,‘b’,‘c’,‘d’\}）

可以看到先是a和a交换了位置(相当于没交换，但也算一种情况)，然后进行递归调用，

从注释4可以看到i+1，可以想到递归调用里面就会依据当前已经交换了的状态(此处a与a交换)继续进行交换，

当然下一步递归调用交换b与b（i变成i+1了嘛），依次类推，但递归交换到最后会到注释2的判断，

发现此时i已经是数组的最后一个元素下标了(即已经没有后续元素给他交换)，因此这样就已经形成了一种排列，输出排列。

好，第一次输出结果输出完了之后，终于有机会到达依次注释5了，从上面结果分析，

第一次全排列输出应该是a,b,c,d因为每一次都是和自己的位置做交换，

下面从第一个跳出递归的地方分析，

第一次跳出来的是c,此时i=2,j=2

(因为（i+1=数组长度-1）之后就符合注释2的判断，形成一种排列，上面说过，最后一个元素已经没有后续元素和他进行交换),

跳出递归后，就在注释5处把交换过的前缀换回来(虽然这里无影响)

然后j++之后，然后继续for循环，此时i=2,j=3，

此时终于交换了不同的元素了！交换的是c与d,然后也是递归调用，但是发现递归下去

也是达到了i+1=数组长度-1 符合注释2的判断，所以此时输出a,b,d,c的排列，好，这里输出完之后，也相应地结束了关于c这一次的递归调用了， 就退到了b(即i=1,j=1)其实到了这里就和上面的一样，继续执行循环体，i=1,j=2，然后交换前缀，

即b与c交换，然后继续递归调用，其实就是在这样的前缀下进行刚刚讲过的递归过程，

当然注意退出递归时，要把之前的交换过的前缀换回来，以便下一次前缀交换。

拓展：  
[https://blog.csdn.net/lemon\_tree12138/article/details/50986990][https_blog.csdn.net_lemon_tree12138_article_details_50986990]  
[https://blog.csdn.net/u013309870/article/details/68941284][https_blog.csdn.net_u013309870_article_details_68941284]

[https_blog.csdn.net_lemon_tree12138_article_details_50986990]: https://blog.csdn.net/lemon_tree12138/article/details/50986990
[https_blog.csdn.net_u013309870_article_details_68941284]: https://blog.csdn.net/u013309870/article/details/68941284