耿老师教你学Java：递归法求全排列

递归法求全排列

耿祥义

本公众号曾发过求全排列的文章：

基于字典序输出全排列-训练常用实用类相关知识

此文是基于字典序的算法，非递归算法。

    n个不同元素的全排列，例如(123...n)!,一共有n!个，例如(123)！一共有3！个，即6个：

    123  132  213  231  312  321

    同一个问题，用递归法和迭代法的时间复杂度是基本一样的,比如求全排列，二者的时间复杂度都是O(n!)（递归涉及到方法（函数）的压栈出栈操作，时间上略微多一些），但递归法的代码简练，而迭代法的代码复杂，甚至有相当的难度。尽管递归涉及到方法（函数）的压栈出栈操作，容易导致栈溢出，但递归算法思想是分治算法思想的重要具体体现（将规模大的问题，逐步分解成规模小的问题，最终解决规模大的问题），是解决许多问题中的首先算法（例如，二叉树的遍历）。

    在计算机算法中，普遍公认的是：“递归”算法和“排序”算法是最重要的两类基本算法。    

1. 递归法求全排列

    求全排列，很容易想到用递归算法。比如：

    （1）！是 1

     对于（12）!,首先降低规模，即将1固定在首位，计算(2)!，然后，再将2固定在首位，计算（1）!,示意如下：

     12    21

     对于（123）!,首先降低规模，即将1固定在首位，计算(23)!，然后，再将2固定在首位，计算（13）!,然后，再将3固定在首位，计算（12）!，示意如下：

     123       132       213       231       312       321

    我门在递归算法中使用了动态数组，即Arrraylist<String> 数组，其优点是，使得递归的代码更加简洁。比如，对于求 (123)! ,递归方法返回的Arrralist<String> 数组表中的节点中依次存放着（123）！的全排列，即Arrraylist<String> 数组表中的节点中的String依次是：

      "123"  "132"   "213"    "231"    "312"   "321"

2.代码与效果

FullPermutatio.java  (封装着递归方法permutatio())

import java.util.*;
public class FullPermutatio {
    public static  List<String> permutatio(int[] source){
           if(source.length == 1) {
               List<String> list = new ArrayList<String>();
               list.add(""+source[0]);
               return list;
           }
           else {
              List<String> list = new ArrayList<String>();
              for(int k=0;k<source.length;k++){
                //source_next是不要数组source的第k个元素的数组：
                 int [] source_next= CopyArray.copyArray(source,k);
                 List<String> listNext = permutatio(source_next);//递归
                 for(int i=0;i<listNext.size();i++) {
                    list.add(source[k]+""+listNext.get(i));//得到的各个排列放到列表里
                 }  
              }
              return list;
           }
    }
}

CopyArray.java

public class CopyArray {
   public static  int [] copyArray(int a[],int k){
        int result[] = new int[a.length-1];
        for(int i=0;i<k;i++) {
            result[i] = a[i];
        } 
        for(int i=k+1;i<a.length;i++) {
            result[i-1] = a[i];
        }
        return result; 
    }
}

MainClass.java

public class MainClass{   
    public static void main(String args[]){
        int [] a = {1,2,3,4,5};
        for(String item:FullPermutatio.permutatio(a)){
             System.out.printf("%-10s",item);
        }
    }
}

• 推荐阅读

• 基于字典序输出全排列-训练常用实用类相关知识
  

• 1至9数字填空与字典序
  

• HannoiTower(汉诺塔)中的神奇之事
  

• Koch 雪花曲线（分形曲线）

  ‍