生成数组的所有排列 | Baeldung中文网

1. 排列简介

排列是指从 n 个元素中有序地选取全部 n 个元素组成一个序列。例如，给定三个字符 A、B、C，我们可以通过排列得到如下六种组合：

ABC, ACB, BAC, BCA, CBA, CAB

这些排列中可能包含有意义的单词（如 CAB），也可能没有。但排列的核心在于“顺序”不同即视为不同排列。

1.1 排列数量

n 个元素的排列总数为 n!（n 的阶乘）。例如：

3 个元素有 3! = 6 个排列
4 个元素有 4! = 24 个排列
10 个元素有 3,628,800 个排列

✅ 注意：排列与组合不同。组合不关心顺序，而排列强调顺序。

1.2 排列增长速度

排列数量随着元素数量呈指数级增长，例如：

元素个数	排列总数
3	6
5	120
10	3,628,800
20	~2.4×10¹⁸

⚠️ 踩坑提醒：如果尝试生成大量元素的所有排列，内存和性能都会成为瓶颈。

1.3 数学表示

排列可以用双行记法表示：

1 2 3 4 5
2 5 4 3 1

表示将 1 换成 2，2 换成 5，5 换成 1，形成一个循环。这种表示方式也被称为循环记法：

(1 2 5)(3 4)

表示两个循环：1→2→5→1 和 3→4→3。

2. 简单递归算法

生成排列最直观的方式是递归：

每次选择一个未使用的元素加入当前排列
递归处理剩余元素
当没有剩余元素时，将当前排列加入结果集

伪代码如下：

algorithm Permutation(GeneratedPermutations, CurrentPermutation, ElementsToPermute):
    if ElementsToPermute not empty:
        for element in ElementsToPermute:
            NextPermutation = CurrentPermutation + element
            RemainingElements = remove element from ElementsToPermute
            Permutation(GeneratedPermutations, NextPermutation, RemainingElements)
    else:
        add CurrentPermutation to GeneratedPermutations

✅ 优点：逻辑清晰，容易实现
❌ 缺点：递归深度大时容易栈溢出，内存消耗高

3. Heap 算法

Heap 算法是一种经典的排列生成算法，通过交换元素生成所有排列，且每个排列只生成一次。

3.1 核心思想

减治策略：先生成 n-1 个元素的所有排列，再将第 n 个元素插入每个可能的位置
每次交换的规则：
- 如果 n 是奇数，交换第一个和最后一个元素
- 如果 n 是偶数，交换第 i 个和最后一个元素

3.2 递归实现

algorithm RecursiveHeapsAlgorithm(Permutations, ElementsToPermute, n):
    if n == 1:
        add ElementsToPermute to Permutations
    else:
        RecursiveHeapsAlgorithm(Permutations, ElementsToPermute, n - 1)
        for i from 0 to n - 1:
            if n is even:
                swap ElementsToPermute[i] and ElementsToPermute[n - 1]
            else:
                swap ElementsToPermute[0] and ElementsToPermute[n - 1]
            RecursiveHeapsAlgorithm(Permutations, ElementsToPermute, n)

✅ 优点：交换次数少，内存占用低
❌ 缺点：排列顺序不是字典序

3.3 非递归实现

algorithm NonRecursiveHeapsAlgorithm(Permutations, ElementsToPermute, n):
    c = new array of size n initialized to 0
    i = 0
    while i < n:
        if c[i] < i:
            if i is even:
                swap ElementsToPermute[0] and ElementsToPermute[i]
            else:
                swap ElementsToPermute[c[i]] and ElementsToPermute[i]
            add ElementsToPermute to Permutations
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1

4. QuickPerm 算法

QuickPerm 是一种基于交换的高效排列生成算法，灵感来自 Heap 排序。

4.1 控制数组

使用一个控制数组 p[] 来控制循环和交换：

p[0] = 0, p[1] = 1, p[2] = 2, ...
每次循环更新 p[i] 并决定交换位置

4.2 算法实现

algorithm CountdownQuickPerm(Permutations, ElementsToPermute, n):
    p = new array of size n+1 initialized to 0 to n
    index = 1
    while index < n:
        p[index] -= 1
        if index is odd:
            j = p[index]
        else:
            j = 0
        swap ElementsToPermute[j] and ElementsToPermute[index]
        add ElementsToPermute to Permutations
        index = 1
        while p[index] == 0:
            p[index] = index
            index += 1

✅ 优点：高效，适合大数据量
❌ 缺点：理解难度略高

5. 字典序排列算法

字典序排列是指按照某种顺序（如字母顺序、数字大小）生成排列。

5.1 Dijkstra 字典序算法

由 Dijkstra 提出，算法步骤如下：

找到最大索引 i，使得 current[i-1] < current[i]
找到最大索引 j，使得 current[j] > current[i-1]
交换 current[i-1] 和 current[j]
反转 current[i..n-1]

5.2 Java 实现伪代码

algorithm GetNextLexographicOrder(CurrentPermutation, n):
    i = n - 1
    while i > 0 and CurrentPermutation[i-1] >= CurrentPermutation[i]:
        i -= 1
    if i <= 0:
        return false
    j = n
    while j > i and CurrentPermutation[j-1] <= CurrentPermutation[i-1]:
        j -= 1
    swap CurrentPermutation[i-1] and CurrentPermutation[j-1]
    i += 1
    j = n
    while i < j:
        swap CurrentPermutation[i-1] and CurrentPermutation[j-1]
        i += 1
        j -= 1
    return true

✅ 优点：按顺序生成，适合需要排序的场景
❌ 缺点：每次生成都要扫描数组，效率略低

6. 总结

生成排列是一个常见但计算量大的问题。本文介绍了以下几种算法：

算法名称	是否递归	是否字典序	优点	缺点
简单递归	✅	❌	易实现	内存占用高
Heap 算法	✅/❌	❌	交换次数少	排列顺序不固定
QuickPerm 算法	❌	❌	高效	理解复杂
字典序排列算法	❌	✅	按顺序生成	每次都要扫描数组

📌 建议：

如果你只需要所有排列，不在乎顺序，推荐使用 Heap 或 QuickPerm
如果你需要按顺序生成排列，推荐使用 字典序排列算法

⚠️ 注意：生成大量排列时务必考虑性能和内存，避免栈溢出或 OOM。

Persistence

REST

Security