数据结构与算法分析的课后习题
编写带有下列声明的例程:
public void permute( String str );
private void permute( char [] str, int low, int high );
第一个例程是驱动程序,它调用第二个例程并显示String str中的字符的所有排列。如果str是"abc",那么输出的串则是abc,acb,bac,bca,cab和cba。第二个例程使用递归。
public class Permute
{public void permute ( String str )
{
permute (str.toCharArray (), 0, str.length ());
String tmp = new StringBuilder ().append (str).reverse ().toString ();
permute (tmp.toCharArray (), 0, tmp.length ());
}
private void permute ( char[] str, int low, int high )
{
if (low == high)
{
return;
}
String result = "";
for ( int i = low; i < high; i++ )
{
result += str[i];
}
if (result.length () < str.length)
{
int count = str.length - result.length ();
for ( int i = 0; i < count; i++ )
{
result += str[i];
}
}
System.out.println (result);
permute (str, ++low, high);
}
public static void main ( String[] args )
{
Permute permute = new Permute ();
permute.permute ("abc");
}
上面的代码,虽然也是方法自己调用自身,但感觉permute (str, ++low, high);这样的调用其实用for循环就能写出来,这个应该不能算是递归吧,
求更好的递归解法
递归和循环本质是都是多次执行,是可以互相替代的,只是递归是另外一种思想,你的代码是递归
但是,你的代码没办法完成的题目中说的结果,递归思想有问题,没有得出全部结果,一个长度为n的个字符不重复的字符串有n!种排列这个应该都知道吧,你可以执行adcd是无法出来24种结果的。下面是我刚才写的一个递归,没仔细查,可能有不对的,map主要是用来去重的
public static void main (String[] args){
String a = "abcd";
test t = new test();
t.permute(a);
}
public void permute ( String str )
{
Map<String,String> m = newPermute(str.substring(1),str.toCharArray()[0]+"");
for (Map.Entry<String, String> entry : m.entrySet()) {
System.out.println(entry.getKey().toString());
}
}
private Map<String,String> newPermute(String string,String a){
Map<String,String> map = new HashMap<String,String>();
char[] str = string.toCharArray();
if(str.length==1){
map.put(str[0]+a,str[0]+a);
map.put(a+str[0],a+str[0]);
return map;
}else{
Map<String,String> m = newPermute(string.substring(1),str[0]+"");
for (Map.Entry<String, String> entry : m.entrySet()) {
String key = entry.getKey().toString();
map.put(a+key,a+key);
map.put(key+a,key+a);
for(int i = 1;i < key.toCharArray().length;i++){
String newKey = key.substring(0,i)+a+key.substring(i);
map.put(newKey,newKey);
}
}
}
return map;
}
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。