全排列算法详细解析
全排列在笔试面试和ACM竞赛中很热门，因为它难度适中，既可以考察递归实现，又能进一步考察非递归的实现，便于区分出考生的水平。（自己的心得：回溯是思想，深搜是本质，递归是实现）
一、全排列的递归实现（以下所有代码以java为主）
以abcd为例，共有24种排列方式，abcd,abdc,acbd,acdb…….，因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。递归的代码如下：
public class Main{
public static int count=0;
public static void swap(char[] a,int i,int j){
char tmp = a[i];
a[i]=a[j];
a[j]=tmp;
}
public static void perm(char[] a,int st,int len){
if(st==len-1){
for(int i=0;i<len;i++){
System.out.print(a[i]);
}
System.out.println("");
count++;
}else{
for(int i=st;i<len;i++){
swap(a,st,i);
perm(a,st+1,len);
swap(a,st,i);
}
}
}
public static void main(String[] args) {
char[] a="abcd".toCharArray();
perm(a,0,4);
System.out.println("总共有："+count+"种");
}
}
运行结果如下：
二、以蓝桥杯里面的一道例题来使用全排列解决
题目：
凑算式: A+B/C+DEF/GHI = 10
这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。比如： 6+8/3+952/714就是一种解法, 5+3/1+972/486是另一种解法。这个算式一共有多少种解法？
代码如下：
public class Main {
static int count=0;
public static void swap(char[] a,int i,int j){
char temp=a[i];
a[i]=a[j];
a[j]=temp;
}
public static boolean check(char[] a){
double[] num = new double[9];
for(int i=0;i<9;i++){
num[i]=a[i]-'0';
}
if(num[0]+num[1]*1.0/num[2]+(num[3]*100+num[4]*10+num[5])*1.0/(num[6]*100+num[7]*10+num[8])==10){
return true;
}
return false;
}
public static void perm(char[] a,int st,int length){
if(st==length-1){
if(check(a)){
count++;
}
}else{
for(int i=st;i<length;i++){
swap(a,st,i);
perm(a,st+1,length);
swap(a,st,i);
}
}
}
public static void main(String[] args) {
char[] a="123456789".toCharArray();
perm(a,0,9);
System.out.println("共有"+count+"种解法");
}
}
运行结果如下：
总结：
全排列就是从第一个数字起每个数分别与它后面的数字交换
