剑指Offer——全排列递归思路

前言

      全排列，full permutation, 可以利用二叉树的遍历实现。二叉树的递归遍历，前中后都简洁的难以置信，但是都有一个共同特点，那就是一个函数里包含两次自身调用。

所以，如果一个递归函数中包含了两次自身调用，那么这类问题就是归纳成二分问题。也就是to be or not to be , is the problem。如果一个使用相同手段并且每一个点上可分为两种情况的问题，基本都可以转化为递归问题。当然，如果是有三个孩子的树，那么我们可能需要在一个递归函数中调用自身三次。

      这里的递归，和我们计算的阶乘又有不一样，因为他没有返回，是发散的。也就是从一个节点，发散到N个节点，我们要的结果是叶子节点。

      计算全排列，我们可以单独拿出每一个元素作为根节点来构成一棵树，所有的可能排列情况就都隐藏在森林中了。现在来看每一颗树，假如4个元素，A，B，C，D，以A为根是第一颗，表示以A开头的排列。

      那么，第二个位置可以选着B，C，D，如果我们选择了B，那么B下还有 C， D可以选择， 如果我们选了C，那么最后只剩下D，这样，就列出第一种。如图所示：

      我们可以看到，这里的孩子个数是递减的，直到最后一个元素，就不用选择了，同时也得到一种可能。

      要枚举出所有的，那么就遍历这样一颗树。好了，先上代码。

  

   

    

     

    
    

     

      package cn.edu.ujn.nk;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public class FullPermutation {
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * recursive method, used for the tree traversal.
     
    
   

    

     

    
    

     

       * 
     
    
   

    

     

    
    

     

       * @param inStr
     
    
   

    

     

    
    

     

       * the elements need to be choose
     
    
   

    

     

    
    

     

       * @param pos
     
    
   

    

     

    
    

     

       * the position of the elements we choose
     
    
   

    

     

    
    

     

       * @param parentData
     
    
   

    

     

    
    

     

       * the elements have been chosen
     
    
   

    

     

    
    

     

       */  
     
    
   

    

     

    
    

     
 public void permutation(String inStr, int pos, StringBuffer parentData) {  
     
    
   

    

     

    
    

     
 if (inStr.length() == 0) {
     
    
   

    

     

    
    

     
 return;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if (inStr.length() == 1) {
     
    
   

    

     

    
    

     

       System.out.println("{" + inStr + "}");
     
    
   

    

     

    
    

     
 return;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 // here we need a new buffer to avoid to pollute the other nodes.
     
    
   

    

     

    
    

     

       StringBuffer buffer = new StringBuffer();
     
    
   

    

     

    
    

     
 // copy from the parent node
     
    
   

    

     

    
    

     

       buffer.append(parentData.toString());
     
    
   

    

     

    
    

     
  
     
    
   

    

     

    
    

     
 // choose the element
     
    
   

    

     

    
    

     

       buffer.append(inStr.charAt(pos));
     
    
   

    

     

    
    

     
  
     
    
   

    

     

    
    

     
 // get the remnant elements. 
     
    
   

    

     

    
    

     

       String subStr = kickChar(inStr, pos);  
     
    
   

    

     

    
    

     
  
     
    
   

    

     

    
    

     
 // got one of the result 
     
    
   

    

     

    
    

     
 if (subStr.length() == 1) {  
     
    
   

    

     

    
    

     

       buffer.append(subStr);  
     
    
   

    

     

    
    

     

       System.out.println(buffer.toString());  
     
    
   

    

     

    
    

     
 return;  
     
    
   

    

     

    
    

     

       }  
     
    
   

    

     

    
    

     
  
     
    
   

    

     

    
    

     
 // here we use loop to choose other children. 
     
    
   

    

     

    
    

     
 for (int i = 0; i < subStr.length(); i++) {  
     
    
   

    

     

    
    

     

       permutation(subStr, i, buffer);  
     
    
   

    

     

    
    

     

       }  
     
    
   

    

     

    
    

     
  
     
    
   

    

     

    
    

     

       }  
     
    
   

    

     

    
    

     
  
     
    
   

    

     

    
    

     
 // a simple method to delete the element we choose 
     
    
   

    

     

    
    

     
 private String kickChar(String src, int pos) {  
     
    
   

    

     

    
    

     

       StringBuffer srcBuf = new StringBuffer();  
     
    
   

    

     

    
    

     

       srcBuf.append(src);  
     
    
   

    

     

    
    

     

       srcBuf.deleteCharAt(pos);  
     
    
   

    

     

    
    

     
 return srcBuf.toString();  
     
    
   

    

     

    
    

     

       }  
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 public static void main(String args[]) {  
     
    
   

    

     

    
    

     

       FullPermutation p = new FullPermutation();
     
    
   

    

     

    
    

     

       StringBuffer buffer = new StringBuffer();
     
    
   

    

     

    
    

     

       String input = "ABCD";
     
    
   

    

     

    
    

     
 for (int i = 0; i < input.length(); i++) {  
     
    
   

    

     

    
    

     

       p.permutation(input, i, buffer);  
     
    
   

    

     

    
    

     

       }  
     
    
   

    

     

    
    

     

       }  
     
    
   

    

     

    
    

     

      }
     
    
  
 

美文美图

文章来源: shq5785.blog.csdn.net，作者：No Silver Bullet，版权归原作者所有，如需转载，请联系作者。

原文链接：shq5785.blog.csdn.net/article/details/52166564