和風(fēng)細(xì)雨

世上本無難事，心以為難，斯乃真難。茍不存一難之見于心，則運(yùn)用之術(shù)自出。

導(dǎo)航

<

2008年3月

>

日

一

二

三

四

五

六

24

25

26

27

28

29

1

2

3

4

5

6

7

9

11

13

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

統(tǒng)計

隨筆 - 99
文章 - 1
評論 - 89
引用 - 0

常用鏈接

留言簿(9)

隨筆分類

隨筆檔案

文章檔案

2007年2月 (1)

相冊

11

搜索

閱讀排行榜

評論排行榜

全排列算法示例

package com.sitinspring;

/**

* 全排列算法示例

如果用P表示n個元素的排列，而Pi表示不包含元素i的排列，(i)Pi表示在排列Pi前加上前綴i的排列，那么，n個元素的排列可遞歸定義為：

如果n=1，則排列P只有一個元素i

如果n>1，則排列P由排列(i)Pi構(gòu)成（i=1、2、

.、n-1）。

根據(jù)定義，容易看出如果已經(jīng)生成了k-1個元素的排列，那么，k個元素的排列可以在每個k-1個元素的排列Pi前添加元素i而生成。

例如2個元素的排列是1 2和2 1，對3個元素而言，p1是2 3和3 2，在每個排列前加上1即生成1 2 3和1 3 2兩個新排列，

p2和p3則是1 3、3 1和1 2、2 1，

按同樣方法可生成新排列2 1 3、2 3 1和3 1 2、3 2 1。

* @author: sitinspring(junglesong@gmail.com)

* @date: 2008-3-25

*/

public class Permutation<T>{

public static void main(String[] args){

String[] arr={"1","2","3"};

Permutation<String> a=new Permutation<String>();

a.permutation(arr,0,arr.length);

}

public void permutation(T[] arr,int start,int end){

if(start<end+1){

permutation(arr,start+1,end);

for(int i=start+1;i<end;i++){

T temp;

temp=arr[start];

arr[start]=arr[i];

arr[i]=temp;

permutation(arr,start+1,end);

temp=arr[i];

arr[i]=arr[start];

arr[start]=temp;

}

else{

for(int i=0;i<end;i++){

System.out.print(arr[i]);

}

System.out.print("\n");

}

posted on 2008-03-25 05:33 和風(fēng)細(xì)雨閱讀(314) 評論(0) 編輯收藏所屬分類: 算法

新用戶注冊刷新評論列表


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




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關(guān)文章: 全排列算法示例考試分?jǐn)?shù)排序的三種排序方式的比較二分查找示例二（對鏈表進(jìn)行查找）二分法查找示例求集合差的幾種算法使用LinkedHashMap進(jìn)行分?jǐn)?shù)排序用匿名類處理分類匯總的方法