一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 552|回复: 3
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
TonyJang 发表于 2014-10-8 11:50:58 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 TonyJang 于 2014-10-8 11:54 编辑
假设str=abcd,输出这四个字母的全部排列方式:

code:
  1. public class Permutation{
  2. private boolean[] used;
  3. private StringBuilder out=new StringBuilder();
  4. private final String in;

  5. public Permutation(final String str){
  6. in=str;
  7. used=new boolean[in.length()];

  8. public void permute(){
  9. if(out.length()==in.length()){
  10. System.out.println(out);

  11. }

  12. for(int i=0;i<in.length();++i){
  13. if(used[i]) continue;
  14. out.append(in.charAt(i));
  15. used[i]=true;
  16. permute();
  17. used[i]=false;
  18. out.setLength(out.length()-1);


  19. }


  20. }

  21. }




  22. }
复制代码
我的思路,第七步除了问题,以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)//不知道对不对?

1guangnian 发表于 2014-10-8 12:45:50 | 显示全部楼层
进入3之后,应该会执行used[2]=false, out.lengt() = 2
然后还在这一层,执行used[3]=true, out = abd,再进入下一层
回复 支持 反对

使用道具 举报

miss_snow 发表于 2014-10-8 18:21:51 | 显示全部楼层
这个代码风格可以是可以,但是很不友好
我稍微改了改,这样子好看点
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;
                        }
                }
        }
最后求大米%>_<%

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 16:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表