Re: 一著名软件公司的java笔试算法题！
原题如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求： "4 "不能在第三位， "3 "与 "5 "不能相连.
我看了回贴都没有很好解决，主要是没有排除重复。
解决思路：强化题目，用1、2、2、3、4、5这六个数字排列“递增”序列。其他要求不变。
算法思路：显然是递归，初始序列122345，先从末两位(45)变化(45,54),然后末三位(345)   ...   直到最后六位.怎样解决重复问题？很简单，由于是递增序列，每生成新序列可与前一生成序列比较，如 <放弃当前序列。当然有更好效率，如预先预测。代码如下：
class   test
{  
    //   当前固定部分
    private   String   CurFixPart;
    private   String   PreGenNum;
   
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);
}
}
序列122345测试通过。
有什么意见请大家多多提点。



------解决方案--------------------
1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2 显然这个结果集还未达到题目的要求。从以下几个方面考虑：
1. 3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。
2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果
3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。

采用二维数组定义图结构，最后的代码是：

import java.util.Iterator;
import java.util.TreeSet;

public class TestQuestion {

private String[] b = new String[]{ "1 ", "2 ", "2 ", "3 ", "4 ", "5 "};
private int n = b.length;