全排列算法——Java实现

2018-03-01 11:07:38来源:oschina作者:刘太刚人点击

分享
什么是全排列

从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。


时间复杂度

n个数(字符、对象)的全排列一共有n!种,所以全排列算法至少时间O(n!)的。如果要对全排列进行输出,那么输出的时间要O(n∗n!),因为每一个排列都有n个数据。所以实际上,全排列算法对大型的数据是无法处理的,而一般情况下也不会要求我们去遍历一个大型数据的全排列。


算法的实现思想

首先,明确一点,本算法使用递归实现的,所以要求对递归有所了解。


当我们要求一组字母的全排列,形如:


【A,B,C,D】


你会怎么做呢?我会这样做:


第一步:将【A,B,C,D】将中的任意一个元素取出;


第二步:从剩下的三个元素中再任意取出一个元素;


第三步:从剩下的两个元素中再任意取出一个元素;


第四步:取出最后一个元素;


这样就可以得到一个【A,B,C,D】排列了!效仿上面的四个步骤,只是不取重复的元素。就可以得到【A,B,C,D】所以的排列了吗?


以此类推,【A】,【A,B】,【A,B,C】,【A,B,C,D,E】,【A,B,C,D,E,...】的全排列也可以一一列出。


到目前为止,细心的你应该可以发现,【A】,【A,B】,【A,B,C】,【A,B,C,D】,【A,B,C,D,E】,【A,B,C,D,E,...】求全排列的方法都是一样的,只是在元素有所差异。所以在写算法时,我们只要写一个函数来求不同的全排列。


实现代码
public class Main {
public static void main(String[] args) {
DataContainer data = new DataContainer(new Character[]{'a', 'b', 'c', 'd'});
Stack res = new Stack<>();
permu(data, res, new Stack());

//打印
for(Object[] objs: res){
for(Object o: objs){
System.out.print(o);
}
System.out.println();
}
}

/**
* 求全排列的函数
* @param data 被排列的数组
* @param res 装载一个排列
* @param objs 装载所有排列
*/
static void permu(DataContainer data, Stack res, Stack objs) {
if (data.effectSize == 0) {
res.push(objs.toArray());
}
for (int i = 0; i < data.actualSize; i++) {
if(data.state(i) == true){
objs.add(data.getElement(i));
permu(data, res, objs);

//回溯
data.recovery(i);
objs.pop();
}
}
}
}
/**
*
* @author liutaigang
*
*/
class DataContainer {
Inner[] inners;
int effectSize;// 有效元素的个数
int actualSize;// 实际元素的个数
DataContainer(Object[] data) {
int len = data.length;
this.actualSize = len;
this.effectSize = len;
inners = new Inner[len];
for (int i = 0; i < len; i++) {
inners[i] = new Inner(data[i], true);
}
}

/**
* @param index 索引
* @return 返回inners中指定的有效值,若无效就返回null
*/
Object getElement(int index){
if(inners[index].state == true){
inners[index].state = false;//取过就无效了
effectSize--;
return inners[index].element;
}
return null;
}

boolean state(int index){
return inners[index].state;
}

/**
* 将指定的元素恢复为有效状态
* @param index 索引
*/
void recovery(int index){
if(inners[index].state == false){
effectSize++;
inners[index].state = true;
}
}

/**
* 内部类
* @author liutaigang
*
*/
class Inner {
Object element;// 元素
boolean state;// 状态:有效——true,无效——false
Inner(Object element, boolean state) {
this.element = element;
this.state = state;
}
}
}
小小的拓展

当然,上述只是全排列的一种实现方法,甚至有些繁杂。仅仅是想为大家提供一种思路。还有一些关于全排列的blog,很值得参考:


http://blog.csdn.net/summerxiachen/article/details/60579623


end

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台