C++实现全排列：非递归与递归算法详解

非递归全排列算法

非递归全排列的核心思想在于找出当前排列的“下一个”字典序更大的排列。其基本步骤如下：

1. 找到序列中最小的一个排列作为起始状态。
2. 从当前排列出发，寻找刚刚比它大一点的下一个排列。
3. 循环执行步骤2，直到找到最大的排列（即逆序排列），此时算法结束。

第1步：确定算法逻辑与辅助函数

为了高效地生成下一个排列，我们需要两个关键操作：交换两个元素的位置，以及将某个区间的数组进行逆序。以下是基础的工具函数定义：

void swap(int* a, int i, int j) {
    // 使用异或运算交换两个整数，避免引入临时变量
    a[i] ^= a[j];
    a[j] ^= a[i];
    a[i] ^= a[j];
}

void reverse(int a[], int i, int j) {
    // 将数组a中下标i到j之间的元素逆序
    for (; i < j; ++i, --j) {
        swap(a, i, j);
    }
}

void print(int a[], int length) {
    for (int i = 0; i < length; ++i)
        cout << a[i] << " ";
    cout << endl;
}

第2步：寻找下一个排列的主逻辑

假设给定序列 P = A1A2...An。要找到下一个排列，具体操作步骤如下：

1. 查找替换点：从低位到高位（从后向前）遍历数组，找到一个位置 i，使得 a[i] < a[i+1]。如果找不到这样的 i，说明当前已经是最大排列（完全降序），算法终止。
   • 目的：找到需要变更的最右侧位置，以保证生成的排列仅比当前大一点点。
2. 查找交换对象：在子数组 a[i+1...n-1] 中，找到一个元素 a[j]，使得 a[j] 是大于 a[i] 的最小值。
   • 原理：由于步骤1中未找到上升点前的部分都是降序的，所以 a[i+1...n-1] 必然是降序排列。因此可以从后往前找第一个大于 a[i] 的元素。
3. 执行交换：交换 a[i] 和 a[j]。
4. 逆序后缀：交换后，a[i+1...n-1] 仍然是降序的（因为之前就是降序，且我们只交换了一个较小的值进来了，或者换了个更小的但保持相对顺序）。为了使其成为该前缀下的最小排列，需要将 a[i+1...n-1] 逆序变为升序。

第3步：完整非递归实现代码

将上述逻辑整合为完整的函数，注意处理边界情况：

void combination(int a[], int length) {
    if (length < 2) return;

    bool end = false;
    while (true) {
        print(a, length);

        int i, j;
        // 步骤1：从右向左找第一个 a[i] < a[i+1]
        for (i = length - 2; i >= 0; --i) {
            if (a[i] < a[i + 1]) break;
            else if (i == 0) return; // 已是最小排列，退出
        }

        // 步骤2：从右向左找第一个大于 a[i] 的 a[j]
        for (j = length - 1; j > i; --j) {
            if (a[j] > a[i]) break;
        }

        // 步骤3 & 4：交换并逆序后缀
        swap(a, i, j);
        reverse(a, i + 1, length - 1);
    }
}

递归全排列算法

递归方法基于分治思想。对于集合 E = {e1, ..., en}，其全排列 perm(E) 可以定义为：
perm(E) = e1·perm({e2,...,en}) + e2·perm({e1,e3,...,en}) + ... + en·perm({e1,...,e(n-1)})
即：固定第一个元素，然后对剩余元素求全排列，依次类推。

第1步：递归基与递归体设计

• 基准情形：当只有一个元素（k == m）时，直接输出当前序列。
  目的：递归的出口，此时已经生成了一个完整的排列。
• 递归情形：当有多个元素（k < m）时：
  1. 将当前位置 k 与后续每个位置 i 的元素交换，相当于枚举当前位的候选元素。
  2. 递归调用 Perm(list, k+1, m)，生成剩余部分的排列。
  3. **回溯**：再次交换回 list[k] 和 list[i]，恢复现场，以便下一次循环使用。

第2步：递归算法完整代码

为了支持不同类型的数据，使用模板实现：

template<class T>
inline void Swap(T& a, T& b) {
    T temp = a; a = b; b = temp;
}

template<class T>
void Perm(T list[], int k, int m) {
    if (k == m) {
        // 输出一个排列方式
        for (int i = 0; i <= m; i++)
            cout << list[i];
        cout << endl;
    } else {
        // 递归地产生这些排列方式
        for (int i = k; i <= m; i++) {
            Swap(list[k], list[i]);   // 交换，固定当前位
            Perm(list, k + 1, m);     // 递归下一位
            Swap(list[k], list[i]);   // 回溯，恢复原状
        }
    }
}

第3步：调用方式

要生成整个数组 list[0:n-1] 的全排列，只需调用 Perm(list, 0, n-1)。
其中 k 表示当前正在处理的前缀结束位置，m 表示数组末尾索引。

总结与对比

非递归算法通过精确控制指针移动和区间逆序，按字典序严格生成下一个排列，不需要额外的栈空间，适合内存受限场景。递归算法代码简洁直观，易于理解其数学定义，但由于存在大量的函数调用栈，对于超大规模数据可能会有性能损耗。在实际开发中，若需快速实现，也可直接使用 C++ STL 提供的 next_permutation 函数，其底层实现逻辑与非递归算法一致。

以上就是C++实现全排列算法（非递归与递归）的详细内容，更多关于C++全排列优化的资料请关注本站其它相关文章！