递归:字符串的全排列,看看我的程序为什么总是出错?

李嘉图 发布于 2013/11/15 10:53
阅读 437
收藏 0

package _20th_ex;

public class Arrange25 {
 private static void f(String s) {
  StringBuffer stringBuffer = new StringBuffer(s);
  f(new StringBuffer(), stringBuffer);
 }

 private static void f(StringBuffer s1, StringBuffer s2) {
  if (s2.length() == 0) {
   System.out.println(s1.toString());
  } else {
   for (int i = 0; i < s2.length(); i++) {
    f(new StringBuffer(s1.append(s2.charAt(i))), new StringBuffer(
      s2.deleteCharAt(i)));
   }
  }
 }

 public static void main(String[] args) {
  f("abc");
 }
}

console在“abc”的情况下总是输出abc/n acb/n

通过分析,发现递归在开始的时候的循环,s2.length()的长度明明是3,但是只循环一次,没道理呀!

各位看看这是怎么回事,小程序而已,不吝赐教!

加载中
0
李嘉图
李嘉图

其实我的思路本来就很对,一开始就是这样,但是必须对s1和s2的副本进行操作。

现在附上我的代码。经测试,完全正确。


package _20th;

public class A {
 private static long count = 0;

 private static void f(String s) {
  // TODO Auto-generated method stub
  StringBuffer stringBuffer = new StringBuffer(s);
  f(new StringBuffer(), stringBuffer);
 }

 private static void f(StringBuffer s1, StringBuffer s2) {
  // TODO Auto-generated method stub
  if (s2.length() == 0) {
   System.out.println(s1.toString());
   count++;
  } else {
   for (int i = 0; i < s2.length(); i++) {
    StringBuffer t1 = new StringBuffer(s1);
    StringBuffer t2 = new StringBuffer(s2);
    t1.append(s2.charAt(i));
    t2.deleteCharAt(i);
    f(t1, t2);
   }
  }
 }

 public static void main(String[] args) {
  f("abcde");
  System.out.println(count);
 }
}
最后count的结果是5*4*3*2*1=120.

OSC首席键客
OSC首席键客
回复 @李嘉图 : 我擦,牛逼啊!这是怎样一种心情呢!
李嘉图
李嘉图
回复 @wenming199 : 谢谢你,同时提醒各位,细节很重要呀,说这句话的时候,我是含着眼泪的,要不然你思路再好也是扯淡!
wenming199
wenming199
回复 @李嘉图 : 这个要求倒是第一次听说,哈哈……总的来说干的不错……
李嘉图
李嘉图
回复 @铂金眼 : 我是想了10几个小时才出的,你们回答好了,我更高兴呀,但是事实是最后还是我找到答案了!我从昨天下午到今天下午,不停地测试,找答案,我付出了很多的!下面的附上代码的我试了,到说这句话的时候都是不太完美的!
OSC首席键客
OSC首席键客
我擦,LZ自己提问,自己回答,然后自己设自己为最佳答案,作弊啊!@红薯
下一页
0
李嘉图
李嘉图
我的程序由于,初始的递归里面的循环只循环一次,导致“abc”输出2个,“abcd”输出3个,”abcde“输出4个,都是因为初始的递归只循环一次,这不科学呀!
0
李嘉图
李嘉图
我从昨天下午,想到今天上午,发现不知道为什么初始的递归只循环一次,为什么?救救我吧!
0
zhizhang007
zhizhang007
你的代码格式看着累眼,就没心情看问题了....
李嘉图
李嘉图
看看吗,自己也可以长进的,在帮助别人的同时。
李嘉图
李嘉图
我的win8.1的ie11,那个插件代码的插件不兼容呀,你可以复制到eclipse里面,然后ctrl+shift+f就行了,那样就舒服了!
0
李嘉图
李嘉图

难道我要出“abc”的递归,需要使用

  f("abc");
  f("bac");
  f("cab");

这不行呀,不符合我的思路呀!

0
李嘉图
李嘉图
别告诉我你们都不用递归,学算法的时候,你们都没听!这不科学呀!
0
吐槽的达达仔
吐槽的达达仔

这代码写的真揪心啊。。。还循环递归new StringBuffer

李嘉图
李嘉图
stringbuffer对于可变字符串的效率比较高!
0
吐槽的达达仔
吐槽的达达仔

你删除的索引是i,删除完以后,字符串索引是不是重建了?

你看看是不是因为这个问题?

0
dsgfdsgf
dsgfdsgf
public class Arrange25 {

	static int i = 0;

	private static void f(String s) {
		if (i < s.length()) {
			System.out.println(s.charAt(i) + s.replace(String.valueOf(s.charAt(i)), ""));
			i++;
			f(s);
		}
	}

	public static void main(String[] args) {
		f("abc");
	}
}
李嘉图
李嘉图
回复 @李日飞 : 3个字符串 全排列是3*2*1=6个,就是A3. abc acb bac bca cab cba
dsgfdsgf
dsgfdsgf
回复 @李嘉图 : 给abc现在输出的是这样 abc bac cab 你想变成什么样
李嘉图
李嘉图
回复 @李日飞 : 全排列!
dsgfdsgf
dsgfdsgf
回复 @李嘉图 : 你要什么样的效果
李嘉图
李嘉图
你的全排列思路很好,貌似效率也比较高,但是依然是错的!
0
wenming199
wenming199

1. For循环里面用递归?

2. 执行完s1="abc",s2="",打印“abc”,然后 返回上一层递归,此时i++; i=1,

s1="ac" s2="b", 然后进入下一层递归,打印出 “acb”,i++,返回上一层递归

发现i=2,For循环已经执行完了,i++,然后返回上一层递归,

此时i=3 s1="",s2="abc" 于是 i<s2.length不成立  程序结束了。

3.问题就出现在程序里的 i 的值不是你预期的那样变化。

wenming199
wenming199
回复 @李嘉图 : 你说的都是每次 i = 0 开始循环的情况,实际情况不是这样,是我说的那样的。 你可以再看看。
wenming199
wenming199
回复 @李嘉图 : 那不就是插空位,先插a , 再插b,有两种情况ab,ba,再插c 有3*2种情况,abc,acb,cab,bac,bca,cba
李嘉图
李嘉图
回复 @wenming199 : 他的这种思路我也会,我是在一个空字符里面按顺序不断地加一个字符进去,作业要求我要这种思路。
李嘉图
李嘉图
假设是对“abc”递归排序,总共会有第一层循环3次,每个第一层包含2第二层,每个第二层包含1个第三层,总共就3*2*1=6。层和层之间怎么会有干涉呢!第一层的第1次循环执行完了,才会i++de,怎么会想你说的那样!
wenming199
wenming199
回复 @李嘉图 : http://pengmj.iteye.com/blog/830978
下一页
返回顶部
顶部