本文共 696 字,大约阅读时间需要 2 分钟。
在解决全排列问题时,当数据规模不大时可以用枚举解决,一旦数据规模很大时(如1000000)这个时候用枚举显得不适合了,运行非常慢,就比如说我要得出1-9的全排列,那么用枚举去解决程序的复杂度O将会是9^9,这样就不合适用枚举了(当然不考虑运行时间的话可以用这个方法),这个时候用递归去实现就比较合适了。先上代码啦
用递归实现全排列
public class FullPermutation{
public static void swap(char[] aa,int index1,int index2){
char t = aa[index1];
aa[index1] = aa[index2];
aa[index2] = t;
}
public static void f(char[] aa,int k){
if(k==aa.length){//设置出口
//可以在下面加入额外条件来对字符进行筛选 比如我想要得到首字符为9的全排列串
//那么只要写上if(aa[0]=='9')即可
System.out.println(String.valueOf(aa));
return;
}
for(int i=k;i<aa.length;i++){
swap(aa,i,k);//依次进行交换
f(aa,k+1);
swap(aa,i,k);//回溯,很重要,
}
}
public static void main(String args[]){
f("123456789".toCharArray(),0);
}
}
递归能够解决的问题有很多,全排列是其中一种,还有博弈问题,迷宫等等。
转载地址:http://uhsni.baihongyu.com/