一、算法描述:
对于n个元素进行全排列,相当于拿出一个元素作为第一个出现的元素(前缀),剩余n-1个元素进行全排列,这样就减少了所求问题的规模,利用递归的思想,最后需要排列的元素个数为一个,进而简化了问题的求解!
void Perm(存放元素的数组List,k记录当前第几个元素作为前缀,m记录待排列元素个数)
Start
if(已经排列到最后一个元素,即k==m){
输出List数组里面的元素
}
else{
for(int i = 0;i小于m;i加一){
//对于重复元素的判断
if(i大于k)//防止自身相等的情况
for(int j=k;j小于i;j加一)
if(List[j]等于List[i])
return;
将List[k]和List[i]交换数值
Perm(List,k+1;k++)//递归运行
将将List[k]和List[i]交换数值
}
}
End
二、代码求解:
package demo;
public class MyCount {
public static int List[] = new int[6];
public static void main(String[] args) {
//赋值操作
for(int i=0;i<6;i++) {
List[i] = 6;
}
List[0]=1;
//进行全排列操作
Perm(List,0,6);
}
//用于进行全排列
public static void Perm(int[] List,int k,int m) {
//用于输出结果
if(k==m) {
for(int i=0;i<m;i++) {
System.out.print(List[i]+"");
}
System.out.println();
}else {
for(int i=k;i<m;i++) {
//对于重复元素的处理情况
if(i>k) {//探寻已经排列的元素中是否出现过现在想排列的数字,以减少重复工作
for(int j=k;j<i;j++) {
if(List[j]==List[i]) {
return;
}
}
}
List[k] = (List[k]+List[i])-(List[i]=List[k]);
Perm(List, k+1, m);
List[k] = (List[k]+List[i])-(List[i]=List[k]);//换回来防止乱序,保证整个过程的层次递进
}
}
}
}
Ending... ...