滕飞

运用递归算法解决数组全排列问题

由于有些问题需要对数组进行全排列，然后存放起来，以便求解相应的问题。
现提供一个我设计的算法，由于该算法的时间复杂度比较高，所以只适用于数组元素个数较少时使用。

该方法的优点为：只需要提供已初始化数组名称和数组的元素个数为参数，即可以将数组元素的全排列结果存放起来或输出。

但该算法有三个缺点：
第一、      在数组初始化的时候，必须先提供一个大于被求数组长度的数组以便能够存放所有求出的数组排列元素。
第二、      由于数组的最大值需要提前设定，数组越界将会容易出现，使用时应该注意。
第三、      由于采用了递归的算法，所以当数组元素增加时，运算量将以指数增加，所以对于数组元素大于某一个值时，将不能用该方法解决全排列问题。
代码如下：（只以整形元素为例）

/*
*对整形数组进行全排列输出
*或存入一维数组
*/

//测试函数//
class All{
     public static void main(String args[]){
           int a[] = new int[10];
           for(int i=0;i<10;i++){     //将数组初始化为1，2，3，4，5//
                 a = i+1;
           }
           AllRunning ar = new AllRunning();
           ar.allFloorRunning(a,5);   //a为数组，4为数组元素个数//
     }
}

//应用函数//
class AllRunning{
     private int MAX_SIZE;
     private int num = 0;
     private int data[] = new int [10000];         //应该设置一个足够容纳数组全部元素的数组//
     // 为了简化allFloor方法的参数个数//
     public void allFloorRunning(int a[],int n){
           int length = this.arrayIn(n);           //获取数组长度//
           //int length = b.length;               //测试b[]是否能返回//
           //System.out.println(length);
           MAX_SIZE = length;
           //System.out.println(MAX_SIZE);
           this.allFloor(a,n,n,0,0);
           this.printArray(data);
     }
     //生成一个足够存储n个数据的全排列的数组//
     private int arrayIn(int n){
           int max = 1;
           for(int i=n;i>=1;i--){
                 max = max * i;
           }
           //System.out.println(max);
           return max;
     }
     private void memory(int a[],int n){     //存储//
           int number = 0;               //总数//
           int figure = 1;               //基数//
           for(int j=n-1;j>=0;j--){
                 number = number + a[j]*figure;
                 figure = figure*10;
           }
           //System.out.print(number+" ");   //检测//
           data[num] = number;
           num++;
     }
     private void printArray(int a[]){
           for(int i=0;i<MAX_SIZE;i++){
                 if(i%5 == 0){
                       System.out.println();
                       System.out.print("a["+i+"]="+a+" ");
                 }
                 else{
                       System.out.print("a["+i+"]="+a+" ");
                 }
           }
     }
     /* a[]为导入数组，m为数组元素个数，将最大值保留至方法结束，
      * n 最初为数组元素个数，然后依次自减，用于控制循环次数，
      * s 为互换控制元素，它与 base 配合。
      * 例如：当 base = 0 时，s 从 0 开始依次自加。
      * 即完成了 a[0] 与 a[0]、a[1]、a[2]、a[3]等的互换。
      **/
     private void allFloor(int a[],int m,int n,int s,int base){
           if(n==2){             //递归结束条件//
                 //Amount.amount(a,m);     //调用输出函数//
                 this.memory(a,m);
                 int md = a[m-n];
                 a[m-n] = a[m-n+1];
                 a[m-n+1] = md;
                             
                 //Amount.amount(a,m);     //调用输出函数//
                 this.memory(a,m);
                 md = a[m-n];
                 a[m-n] = a[m-n+1];
                 a[m-n+1] = md;
           }
           else if(n>2){           //运用递归算法//
                 for(int i=0;i<n;i++,s++){
                       int middle = a[base];
                       a[base] = a[s];
                       a[s] = middle;
                       allFloor(a,m,n-1,base+1,base+1);//递归算法//
                       middle = a[base];
                       a[base] = a[s];
                       a[s] = middle;
                 }
           }
           else{
                 System.out.println("输入错误，请重新输入");
           }
           System.out.println();
     }
}
class Amount{
     public static void amount(int a[],int n){
           int num = 0;     //总数//
           int figure = 1;
           for(int i=n-1;i>=0;i--){
                 num = num + a*figure;
                 figure = figure*10;
           }
           System.out.print(num+" ");
     }
}