字符串的全排列，用递归，没看懂，思路和题目都在这儿，求解答

假设str=abcd，输出这四个字母的全部排列方式：

code：

1. public class Permutation{
   
2. private boolean[] used;
   
3. private StringBuilder out=new StringBuilder();
   
4. private final String in;
   
5. 
   
6. public Permutation(final String str){
   
7. in=str;
   
8. used=new boolean[in.length()];
   
9. 
   
10. public void permute(){
    
11. if(out.length()==in.length()){
    
12. System.out.println(out);
    
13. 
    
14. }
    
15. 
    
16. for(int i=0;i<in.length();++i){
    
17. if(used[i]) continue;
    
18. out.append(in.charAt(i));
    
19. used[i]=true;
    
20. permute();
    
21. used[i]=false;
    
22. out.setLength(out.length()-1);
    
23. 
    
24. 
    
25. }
    
26. 
    
27. 
    
28. }
    
29. 
    
30. }
    
31. 
    
32. 
    
33. 
    
34. 
    
35. }

复制代码

我的思路，第七步除了问题，以abcd为例：

1）out=a,used[0]=true;
2）out=ab,used[1]=true;
3）out=abc,used[2]=true;
4）out=abcd,used[3]=true;
5）再进入permute（），执行if循环，输出abcd，return回上一层，即4）
6）out=abcd,used[3]=false,out.length()=3
7）for循环结束之后进入3）//不知道对不对？

进入3之后，应该会执行used[2]=false, out.lengt() = 2
然后还在这一层，执行used[3]=true, out = abd，再进入下一层

这个代码风格可以是可以，但是很不友好
我稍微改了改，这样子好看点
public void permute(){
        if(out.length()==in.length()){
                System.out.println(out);
        } else {
                for(int i=0;i<in.length();++i){
                        if(used[i])
                                continue;
                        out.append(in.charAt(i));
                        used[i]=true;
                        permute();
                        used[i]=false;
                        out.setLength(out.length()-1);
                }
        }
}
虽说没有太大的差别O(∩_∩)O哈！
不过我自己写全排列，更倾向于这么写
        // arr [0 .. len-1] 是字符串转化的一个int[]或者char[]字符串
        // 调用的时候就用permute(0,arr);
        public static void permute(int currentPosition, int[] arr) {
                if (currentPosition == arr.length) {
                        // 当前情况排列已经结束
                        for (int i = 0; i < arr.length; i++)
                                System.out.printf("%3d ", arr[i]);
                        System.out.println();
                } else {
                        // 继续递归排列
                        int temp;
                        for (int i = currentPosition; i < arr.length; i++) {
                                // 交换后续每一个字符串，轮着当第currentPosition个
                                temp = arr[currentPosition];
                                arr[currentPosition] = arr[i];
                                arr[i] = temp;

                                permute(currentPosition + 1, arr);

                                // 交换回来，继续迭代，让后面的接着当地currentPosition个
                                temp = arr[currentPosition];
                                arr[currentPosition] = arr[i];
                                arr[i] = temp;
                        }
                }
        }
最后求大米%>_<%

lz的这个方法我大概知道是什么意思，后面那个理解应该是对的
充分理解递归的作用
这里递归的实现其实和我们正常理解的全排列是一样的
整个是一个大循环
1、先第一层递归，abcd轮着当第一个
第一个先定下a 然后递归把后面的全排列
2、这层递归里面是bcd轮着当第二个
先定下b
………………
一共有四层实际进行for循环的递归
第五层就不再递归进行下去了
  if(out.length()==in.length()){
                System.out.println(out);
}
用这个直接输出
就是我们用大脑模拟的方法
不过lz的这个开的数组太多，略微有些多余，但是方便理解，相比于我后面提供的那个
希望对lz有帮助~~~