@toc
递归全排列问题（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; | |
| } | |
| } |
- 时间复杂度
$$T(n) = \begin{cases}
θ(1) & n = 1 \
nT(n – 1) + n & n > 1 \
\end{cases}$$
2. 固定元素找位置
- 算法思想
1. 首先，我们把 n 放在的位置P1上，并且用子数组P2..n来产生前n-1个数的排列
2. 接着，我们将 n 放在P2上，并且用子数组P1和P3..n来产生前n-1个数的排列
3. 然后，我们将 n 放在P3上，并且用子数组P1..2和P4..n来产生前n-1个数的排列
4. 重复上述过程直到我们将 n 放在Pn上，并且用子数组P1..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; | |
| } | |
| } | |
| } | |
| } |
- 时间复杂度
$$T(n) = \begin{cases}
θ(1) & n = 1 \
nT(n – 1) + n & n > 1 \
\end{cases}$$
正文完