在 C++ 中生成数组排列的不同方法

排列组合就像组合学的魔杖，让我们能够探索元素如何在数组中重新排列。知道如何生成数组的所有排列是一项有用的技能，无论我们是程序员、数学爱好者，还是试图解决难题的人。在本文中，我们将学习许多生成数组排列的方法。

数组排列的含义是什么？

假设我们希望用字母 A、B 和 C 创建一个单词。它们可以排列成各种配置，称为排列。选项如下：ABC、ACB、BAC、BCA、CBA 和 CAB。顺序在排列中很重要，这就是它的全部意义。

重要的是，有时人们将排列称为 i 而不是组合。然而，在数学中存在区别。组合是由不考虑其顺序而选择的项组成的。例如，如果我们掷两个骰子并查看总和，无论我们掷出三和四还是四和三，结果都是相同的。在该组合中，顺序无关紧要。

可以生成多少种排列？

集合或数组的大小决定了可以从给定的一组组件中生成多少种排列。一个由 “n” 个不同元素组成的集合中，一次取 “r” 个元素的排列数可以在组合学中通过以下公式找到：

其中

• P(n,r) 表示排列数。
• n 是不同元素的总数。
• r 是一次取出的元素数量。
• n!（读作“n 阶乘”）表示从 1 到 n 的所有正整数的乘积。

如果我们希望生成给定集合的每个排列（其中“r”等于“n”），则公式简化为：

换句话说，我们可以为一组“n”个不同组件创建 “n!”（n 阶乘）种排列。随着“n”的增加，排列的数量迅速增加。例如，如果我们有 3 个项目，则有 3! = 6 种排列；如果我们有 4 个元素，则有 4! = 24 种排列，依此类推。

1. 使用 <algorithm> 中的 std::next_permutation

在此方法中，C++ 中的 <algorithm> 头文件提供了一个方便的函数来生成排列。

示例

输出

说明

在此示例中，std::next_permutation 生成下一个按字典顺序更大的排列，并且在没有更多排列时返回 false，这是此方法的基础。

2. 递归回溯

我们可以实现递归回溯算法来生成排列。

示例

输出

说明

在此示例中，此方法使用递归调用和回溯来生成所有可能的排列。

3. Heap's 算法

Heap's 算法是一种迭代算法，用于生成排列。它基于交换元素。

示例

输出

说明

在此示例中，Heap's 算法使用迭代循环和交换非递归地生成排列。