递归全排列问题（两种方法 Java实现）

大家好，欢迎来到IT知识分享网。

递归全排列问题（Java实现）

问题描述

生成 {1,2,…,n} 的所有 n! 个排列

算法

1. 固定位置放元素

算法思想

生成元素{2,3,…,n}的所有排列，并且将元素1放到每个排列的开头
生成元素{1,3,…,n}的所有排列，并将数字2放到每个排列的开头
重复这个过程，直到元素{2,3,…,n-1}的所有排列都产生，并将元素n放到每个排列的开头
Java源代码

/* * 若尘 */ package perm; import java.util.Arrays; / * 全排列问题（递归） * @author ruochen * @version 1.0 */ public class GeneratiingPerm { public static int count = 0; public static void main(String[] args) { char[] arr = {'a', 'b', 'c'}; int start = 0; int end = arr.length - 1; perm(arr, start, end); System.out.println("共有 " + count + " 种排列方式"); } / * 实现全排列 * @param arr 待求全排列数组 * @param start 开始位置 * @param end 结束位置 */ public static void perm(char[] arr, int start, int end) { if (start == end) { count++; System.out.println(Arrays.toString(arr)); } else { for (int i = start; i <= end; i++) { swap(arr, start, i); perm(arr, start + 1, end); // 为了排列不会丢失，我们这里在交换回来，使得每次都是以一个固定序列开始 swap(arr, start, i); } } } / * 交换两个数组元素 * @param arr 数组 * @param i 第一个元素下标 * @param j 第二个元素下标 */ public static void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } 

时间复杂度

2. 固定元素找位置

算法思想
首先，我们把 n 放在的位置P[1]上，并且用子数组P[2..n]来产生前n-1个数的排列
接着，我们将 n 放在P[2]上，并且用子数组P[1]和P[3..n]来产生前n-1个数的排列
然后，我们将 n 放在P[3]上，并且用子数组P[1..2]和P[4..n]来产生前n-1个数的排列
重复上述过程直到我们将 n 放在P[n]上，并且用子数组P[1..n]来产生前n-1个数的排列
Java源代码

public static void perm2(char[] arr, int start, int end) { if (end == 0) { System.out.println(Arrays.toString(arr)); } else { for (int i = start; i <= end; i++) { if (arr[i] == 0) { arr[i] = (char) end; perm2(arr, start, end - 1); arr[i] = 0; } } } } 

时间复杂度