posts - 73, comments - 55, trackbacks - 0

/*

?*?原題如下：用1、2、2、3、4、6這六個數字，用java寫一個main函數，打印出所有不同的排列，

?*?如：612234、412346等，要求："4"不能在第三位，"3"與"6"不能相連.?

?*?

?*?1?把問題歸結為圖結構的遍歷問題。實際上6個數字就是六個結點，把六個結點連接成無向連通圖，對于每一個結點求這個圖形的遍歷路徑，

?*?所有結點的遍歷路徑就是最后對這6個數字的排列組合結果集。?

?*?2?顯然這個結果集還未達到題目的要求。從以下幾個方面考慮：?

?*?1.?3，6不能相連：實際要求這個連通圖的結點3，5之間不能連通,?可在構造圖結構時就滿足改條件，然后再遍歷圖。?

?*?2.?不能有重復:?考慮到有兩個2，明顯會存在重復結果，可以把結果集放在TreeSet中過濾重復結果?

?*?3.?4不能在第三位:?仍舊在結果集中去除滿足此條件的結果。

? */

import ?java.util.Iterator;

import ?java.util.TreeSet;

public ? class ?Test? {

? private ?String[]?b? = ? new ?String[]? {? " 1 " ,? " 2 " ,? " 2 " ,? " 3 " ,? " 4 " ,? " 6 " ?} ;

? private ? int ?n? = ?b.length;

? private ? boolean []?visited? = ? new ? boolean [n];

? private ? int [][]?a? = ? new ? int [n][n];

? private ?String?result? = ? "" ;

? private ?TreeSet?set? = ? new ?TreeSet();

? public ? static ? void ?main(String[]?args)? {

?? new ?Test().start();

?}

? private ? void ?start()? {

?? // ?Initial?the?map?a[][]

?? for ?( int ?i? = ? 0 ;?i? < ?n;?i ++ )? {

??? for ?( int ?j? = ? 0 ;?j? < ?n;?j ++ )? {

???? if ?(i? == ?j)? {

?????a[i][j]? = ? 0 ;

????} ? else ? {

?????a[i][j]? = ? 1 ;

????}

???}

??}

?? // ?3?and?5?can?not?be?the?neighbor.

??a[ 3 ][ 5 ]? = ? 0 ;

??a[ 5 ][ 3 ]? = ? 0 ;

?? // ?Begin?to?depth?search.

?? for ?( int ?i? = ? 0 ;?i? < ?n;?i ++ )? {

??? this .depthFirstSearch(i);

??}

?? // ?Print?result?treeset.

??Iterator?it? = ?set.iterator();

?? while ?(it.hasNext())? {

???String?string? = ?(String)?it.next();

???System.out.println(string);

??}

?}

? private ? void ?depthFirstSearch( int ?startIndex)? {

??visited[startIndex]? = ? true ;

??result? = ?result? + ?b[startIndex];

?? if ?(result.length()? == ?n)? {

// ???"4"?can?not?be?the?third?position.

??? if ?(result.indexOf( " 4 " )? != ? 2 )? {

// ????Filt?the?duplicate?value.

????set.add(result);

???}

??}

?? for ?( int ?j? = ? 0 ;?j? < ?n;?j ++ )? {

??? if ?(a[startIndex][j]? == ? 1 ? && ?visited[j]? == ? false )? {

????depthFirstSearch(j);

???}

??}

?? // ?restore?the?result?value?and?visited?value?after?listing?a?node.

??result? = ?result.substring( 0 ,?result.length()? - ? 1 );

??visited[startIndex]? = ? false ;

?}

}

只要這樣定義圖，根本不用在代碼中寫IF ELSE語句。
實際上基于圖的算法好處在于，只要你能定義好滿足題目要求的圖結構，遍歷的結果就是你要的結果，不用任何對遍歷結果做任何處理。包括本題中的：4不能在第三位置，3，5不能相連，唯一性要求，其實都可以在體現在構造的圖形結構里，然后直接遍歷圖取得自己要的結果。而不用再次處理結果集。只是說這里實際上對其它要求要體現在圖結構里有困難（理論上是可以的），但起碼3，5不能相接是很好構造的，就是上面的代碼段來解釋的。

關于圖形數據結構建議先看看數據結構的書，主要是將如何利用二維數組描述圖結構，再看看圖的深度遍歷實現原理。最后再應用到這個問題上來，自然就不難明白了。

posted on 2007-03-02 17:37 保爾任閱讀(2388) 評論(0) 編輯收藏所屬分類: Arithmetic & Data Structure

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 求兩個數或多個數的最大公約數算法及其實現組合數學－Catalan數 java用字節數截取字符串 java兩個字符串的最大公共自串字符串匹配 java整型數組平衡點算法 java字符串全排列問題（經典）動態規劃算法二叉樹如何求素數

<

2007年3月

>

日

一

二

三

四

五

六

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

7

常用鏈接

留言簿(4)

隨筆分類

隨筆檔案

文章分類

文章檔案

搜索

最新評論

閱讀排行榜

評論排行榜