1. 简介
本文将探讨如何在 Java 中生成数组的 全排列。
首先，我们会定义什么是“全排列”；其次，分析一些限制条件；最后，重点介绍三种生成方式：递归法、迭代法和随机打乱法。
由于我们主要关注 Java 实现，因此不会深入数学细节。
2. 什么是全排列？
一个集合的全排列指的是其元素的所有可能排列顺序。如果集合有 n 个元素，则总共有 n! 种排列方式。这里的 n! 是阶乘，即小于等于 n 的所有正整数的乘积。
2.1. 示例
以整型数组 [3,4,7] 为例：
- 元素数量：3
- 排列总数：3! = 1 × 2 × 3 = 6
具体排列如下：
[3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]
2.2. 性能约束 ⚠️
随着 n 增大，全排列的数量增长极快。例如：
✅ 十个元素的排列只需几秒即可生成
❌ 而十五个元素则需要两周时间才能全部列出：
3. 实现算法
3.1. 递归算法（Heap 算法）
第一个介绍的是著名的 Heap 算法，它是一种递归方法，通过每次交换一个元素来生成所有排列。
⚠️ 注意：该方法会修改原数组。如果不希望改变输入数组，应在调用前创建副本。
public static <T> void printAllRecursive(
int n, T[] elements, char delimiter) {
if(n == 1) {
printArray(elements, delimiter);
} else {
for(int i = 0; i < n-1; i++) {
printAllRecursive(n - 1, elements, delimiter);
if(n % 2 == 0) {
swap(elements, i, n-1);
} else {
swap(elements, 0, n-1);
}
}
printAllRecursive(n - 1, elements, delimiter);
}
}
辅助方法如下：
private static void swap(T[] elements, int a, int b) {
T tmp = elements[a];
elements[a] = elements[b];
elements[b] = tmp;
}
private static void printArray(T[] elements, char delimiter) {
String delimiterSpace = delimiter + " ";
for(int i = 0; i < elements.length; i++) {
System.out.print(elements[i] + delimiterSpace);
}
System.out.print('\n');
}
📌 当前是打印到控制台，你也可以轻松地将其结果保存到 List 或数组中。
3.2. 迭代算法（Heap 算法变种）
Heap 算法同样可以使用迭代实现：
int[] indexes = new int[n];
for (int i = 0; i < n; i++) {
indexes[i] = 0;
}
printArray(elements, delimiter);
int i = 0;
while (i < n) {
if (indexes[i] < i) {
swap(elements, i % 2 == 0 ? 0: indexes[i], i);
printArray(elements, delimiter);
indexes[i]++;
i = 0;
}
else {
indexes[i] = 0;
i++;
}
}
3.3. 按字典序生成排列 ✅
如果数组中的元素具有可比较性，我们可以生成按自然顺序排序的排列：
public static <T extends Comparable<T>> void printAllOrdered(
T[] elements, char delimiter) {
Arrays.sort(elements);
boolean hasNext = true;
while(hasNext) {
printArray(elements, delimiter);
int k = 0, l = 0;
hasNext = false;
for (int i = elements.length - 1; i > 0; i--) {
if (elements[i].compareTo(elements[i - 1]) > 0) {
k = i - 1;
hasNext = true;
break;
}
}
for (int i = elements.length - 1; i > k; i--) {
if (elements[i].compareTo(elements[k]) > 0) {
l = i;
break;
}
}
swap(elements, k, l);
Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length));
}
}
📌 此算法在每一步都执行了 reverse 操作，因此相比 Heap 算法效率略低。
3.4. 随机排列算法 🎲
当 n 很大时，直接生成所有排列不现实。这时我们可以采用随机打乱的方式生成样本排列：
Collections.shuffle(Arrays.asList(elements));
你可以多次运行此方法以生成多个随机排列。
⚠️ 可能出现重复排列，但对于大 n 来说，概率非常小。
4. 小结
本文介绍了多种生成数组全排列的方法，包括递归与迭代版本的 Heap 算法，以及按字典序排序的排列生成方式和随机打乱法。
对于大规模数据，推荐使用随机生成策略。
本文章中所有代码片段均可在我们的 GitHub 仓库 中找到。