递归求解:n个元素的全排列问题

    科技2022-07-31  100

    一、算法描述:

    对于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... ...

    Processed: 0.010, SQL: 8