?

原題如下：用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. 先對1，2，2，3，4，5 全排序。 把結果存到一個數組里面去。

數組的元素是一個string. 比如 122345, 522413 等等

2. 歷遍整個數組用正規表達式去判斷這個元素是不是符合規格

比如 122435

規則1 。 match=[//d][//d][//d][4]

規則2。 match=[35]|[53]

如果正規表達式匹配的結果數大于0，說明這個元素不是我們要得

當匹配的結果等于0，則把這個元素加入一個新的集合中去

3. 新的集合就是我們要得結果集

?

好處： 1不要動腦子想，思路清楚。 2對于數字，字符，都適合。 3。規則的修改快速，比如要求改為第4位不能為1， 2和3不能相鄰等， 只學要改規則就可以了。

本文轉自左正博客園博客，原文鏈接：http://www.cnblogs.com/soundcode/archive/2010/12/19/1910307.html，如需轉載請自行聯系原作者