耿老师教你学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);        }    }}