The following article is from Java教学与小提琴耿祥义 Author 耿祥义
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);}}}