一个公司面试题的算法

Question

用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);
} 
} 
谁能解释下这个算法什么意思，希望详细一点，我看了大半天，越看越晕乎，主要解释这个算法是怎样遍历每一种可能的组合的，按照什么样的规律去遍历这些组合，小生有礼了

Answer 1

public class test0 
{ 
  // 当前固定部分 
  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);
} 
} 
不好意思，这是完整的程序，。。

Answer 2

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);
}
}

Answer 3

从main方法开始讲
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呢???我也不知道...走了半天我也混了..底下再递归...呵呵我仔细看看啊...

Answer 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