一个递归算法

Question

编写带有下列声明的例程：
public void permute（String str）；
private void permute（char[] str,int low,int high);
第一个例程是个驱动程序，他调用第二个例程并显示String str中的字符的所有排列。如果str是“abc”，那么输出的则是abc,acb,bca,bac,cab和cba。第二个例程使用递归。

Answer 1

  public void permute(String str){
    char[] cs=str.toCharArray();
    permute(cs,0,cs.length-1);
  }
  private void permute(char[] str,int low,int high){
    if(low==high) System.out.println(str);
    for(int i=low;i<=high;i++){
      if(i>low){//交换
        str[low]^=str[i];
        str[i]^=str[low];
        str[low]^=str[i];
      }
      permute(str,low+1,high);
      if(i>low){//换回来,还原数据
        str[low]^=str[i];
        str[i]^=str[low];
        str[low]^=str[i];
      }
    }
  }

Answer 2

的确很强！^这个符号是异或的意思，1^1=0,0^0=0,1^0=1
使用异或来完成字符的交换，省掉了中间变量temp，节省了存储空间
str[low]^=str[i]; 
str[i]^=str[low]; 
str[low]^=str[i]; 
就相当于
temp = str[i];
str[i] = str[low];
str[low] = temp;

Answer 3

递归函数的第一行:if(low==high) System.out.println(str); 
代表递归处理的终结:一个数的排列只有一种;
其后的处理简单说就是把low到high之间的数轮流放在low的位置上,并要求计算余下从low+1到high之间的排列,如此递归直到low==high则递归终结,输出结果.
注意:由于使用^=来进行数据交换,那么if(i>low)的判断非常重要,否则会出错.