Posted on 2008-03-25 05:46
博学精思慎言笃行 阅读(147)
评论(1) 编辑 收藏 所属分类:
算法数据结构
package com.sitinspring;
/**
* 全排列算法示例
如果用P表示n个元素的排列，而Pi表示不包含元素i的排列，(i)Pi表示在排列Pi前加上前缀i的排列，那么，n个元素的排列可递归定义为：
如果n=1，则排列P只有一个元素i
如果n>1，则排列P由排列(i)Pi构成（i=1、2、
.、n-1）。
根据定义，容易看出如果已经生成了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{
public static void main(String[] args){
String[] arr={"1","2","3"};
Integer[] arr02={4,5,6,7};
permutation(arr02,0,arr02.length);
}
public static void permutation(Object[] arr,int start,int end){
if(start<end+1){
permutation(arr,start+1,end);
for(int i=start+1;i<end;i++){
Object 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");
}
}
}