用java语言实现,一个组数:122345这6个数,打印出它所有可能的组合;要求4不能在第3位,3和5不能相连
算法如下
public void GenControll(String Base)
{
PreGenNum="0";
CurFixPart="";
GenNext(Base, 0);
} void GenNext(String varPart, int curPos)
{
if (varPart.length()==2)
{
Validate(varPart);
Validate(shift(varPart, 1));
return;
}
// Next Layer
String newGen=shift(varPart, curPos);
String SavedFixPart=CurFixPart;
CurFixPart=CurFixPart+newGen.substring(0,1);
GenNext(newGen.substring(1), 0);
CurFixPart=SavedFixPart;
// 同层递增
if (curPos==varPart.length()-1)
return;
GenNext(varPart, curPos+1);
}
}
谁能解释下这个算法什么意思,希望详细一点,我看了大半天,越看越晕乎,主要解释这个算法是怎样遍历每一种可能的组合的,按照什么样的规律去遍历这些组合,小生有礼了
算法如下
public void GenControll(String Base)
{
PreGenNum="0";
CurFixPart="";
GenNext(Base, 0);
} void GenNext(String varPart, int curPos)
{
if (varPart.length()==2)
{
Validate(varPart);
Validate(shift(varPart, 1));
return;
}
// Next Layer
String newGen=shift(varPart, curPos);
String SavedFixPart=CurFixPart;
CurFixPart=CurFixPart+newGen.substring(0,1);
GenNext(newGen.substring(1), 0);
CurFixPart=SavedFixPart;
// 同层递增
if (curPos==varPart.length()-1)
return;
GenNext(varPart, curPos+1);
}
}
谁能解释下这个算法什么意思,希望详细一点,我看了大半天,越看越晕乎,主要解释这个算法是怎样遍历每一种可能的组合的,按照什么样的规律去遍历这些组合,小生有礼了
{
// 当前固定部分
private String CurFixPart;
private String PreGenNum;
public static void main(String[] args)
{
test0 t=new test0();
t.GenControll("122345");
} // 调整字符串s位置pos字符到最前
private String shift(String s, int pos)
{
String newStr;
if (s.length()>pos+1)
newStr=s.substring(pos, pos+1)
+s.substring(0, pos)
+s.substring(pos+1);
else
newStr=s.substring(pos)
+s.substring(0, pos);
return newStr;
} protected int Validate(String newNum)
{
String newGenNum=CurFixPart+newNum;
if (Integer.valueOf(newGenNum)<=Integer.valueOf(PreGenNum))
return 0;
if (newGenNum.substring(2,3).equals("4") ||
(newGenNum.indexOf("35")!=-1) || (newGenNum.indexOf("53")!=-1))
return 0;
PreGenNum=newGenNum;
System.out.println(newGenNum);
return 0;
} public void GenControll(String Base)
{
PreGenNum="0";
CurFixPart="";
GenNext(Base, 0);
} void GenNext(String varPart, int curPos)
{
if (varPart.length()==2)
{
Validate(varPart);
Validate(shift(varPart, 1));
return;
}
// Next Layer
String newGen=shift(varPart, curPos);
String SavedFixPart=CurFixPart;
CurFixPart=CurFixPart+newGen.substring(0,1);
GenNext(newGen.substring(1), 0);
CurFixPart=SavedFixPart;
// 同层递增
if (curPos==varPart.length()-1)
return;
GenNext(varPart, curPos+1);
}
}
不好意思,这是完整的程序,。。
public class test {
// 当前固定部分
private String CurFixPart;
private String PreGenNum; /**
* @param args
*/
public static void main(String[] args) {
test t = new test();
t.GenControll("122345");
} // 调整字符串s位置pos字符到最前
private String shift(String s, int pos) {
String newStr;
if (s.length() > pos + 1){
newStr = s.substring(pos, pos + 1) + s.substring(0, pos)
+ s.substring(pos + 1);
}
else{
newStr = s.substring(pos) + s.substring(0, pos);
}
return newStr;
} protected int Validate(String newNum) {
String newGenNum = CurFixPart + newNum;
if (Integer.valueOf(newGenNum) <= Integer.valueOf(PreGenNum))
return 0;
if (newGenNum.substring(2, 3).equals("4")
|| (newGenNum.indexOf("35") != -1)
|| (newGenNum.indexOf("53") != -1))
return 0; PreGenNum = newGenNum;
System.out.println(newGenNum);
return 0;
} public void GenControll(String Base) {
PreGenNum = "0";
CurFixPart = "";
GenNext(Base, 0);
} void GenNext(String varPart, int curPos) {
if (varPart.length() == 2) {
Validate(varPart);
Validate(shift(varPart, 1));
return;
}
// Next Layer
String newGen = shift(varPart, curPos);
String SavedFixPart = CurFixPart;
CurFixPart = CurFixPart + newGen.substring(0, 1);
GenNext(newGen.substring(1), 0);
CurFixPart = SavedFixPart;
// 同层递增
if (curPos == varPart.length() - 1)
return;
GenNext(varPart, curPos + 1);
}
}
1.Test t = new Test();
2.t.GenControll("1234");
这两句
1. 实例化对象.
2. 传入要组合排序的字符串然后进入GenControll方法
1.PreGenNum = "0";
2.CurFixPart = "";
3.GenNext(Base, 0);
这三句.
前两句定义了两个成员变量string类型..
最后一句调用了.GenNext(Base, 0);这里Base的值是"1234".就是我们传入的字符串的值现在我们来看GenNext(String varPart, int curPos)方法.
首先进入他需要一个验证就是
if (varPart.length() == 2) {
Validate(varPart);
Validate(shift(varPart, 1));
return;
}如果传入的字符串varPart的长度是2的话.他要调用
Validate(String)方法..这个方法.主要是
将传入的String和之前的String进行拼接成一个整数..
String newGenNum = CurFixPart + newNum;
PreGenNum = newGenNum;
System.out.println(newGenNum);
return 0;然后我们看看shift(varPart, 1)这个方法想要做什么
他给的注释是:调整字符串s位置pos字符到最前
直接给你个结果你一定就能看懂
shift("1234", 1) = 2134
shift("1234", 2) = 3124所以这个if的意思就是如果前几位固定好了..只剩下最后两位的时候..
进行if里面的打印
比如
12345前123固定好了
GenNext("45", x) ;
这时候走if
他就会根据走Validate("45"),Validate("54") ;
于是如果条件满足就会打印
13245 和 12354然后继续往下走
String newGen = shift(varPart, curPos);
这个方法我们刚才说过了..就是把curPos位置的字符放到最前面CurFixPart;这个是存放那些固定好的前缀.String SavedFixPart = CurFixPart;
这句话将savedFixPart指向CurFixPart .属于一个零时存储把因为下面要修改CurFixPart的值CurFixPart = CurFixPart + newGen.substring(0, 1);这句话将CurFixPart值截取出了第一个.在我们的实例中是1GenNext(newGen.substring(1), 0);就相当于GenNext("321",0); 这就是地递归了
同上最后调用到GenNext("21",0);这时候会打印出43214312方法return他就会走掉上一层方法中既走
CurFixPart = SavedFixPart;
// 同层递增
if (curPos == varPart.length() - 1)
return;
GenNext(varPart, curPos + 1);这段方法这里注意的是 CurFixPart = SavedFixPart;SavedFixPart的值会是多少???这里是他的第一个数字就是4
为什么是4呢???我也不知道...走了半天我也混了..底下再递归...呵呵我仔细看看啊...
他的思路就是...
首先四个数字
4321
一直递归到最后两位,然后将两位互换位置打印出
4321
4312
然后根据
GenNext(varPart, curPos + 1);
String newGen = shift(varPart, curPos);
这两句将 2和3 互换位置 于是以42开头的打印
4231
4213
然后根据
GenNext(varPart, curPos + 1);
String newGen = shift(varPart, curPos);
将1和2互换位置打印出
4132
4123
这样以4开头的都打印完了
if (curPos == varPart.length() - 1)
return;
此方法结束
这时候他会调用 GenNext("4321", 1);
将3提到最前面..同上递归..我试试能不能写出个比他简单的方法吧..这个读起来好费劲啊..我表达也不好
3421
3412
3241
3214