在 C++ 中按字典序打印所有排列

在本文中，您将学习如何在 C++ 中以排序（字典序）顺序打印所有排列，并附带示例。但在进行实现之前，您必须了解 C++ 中的排列和字典序。

什么是排列？

排列 是计算机科学和组合学中的一个基本概念。它们是按特定顺序排列的项目集，算法设计中常见的挑战是确定一组元素的所有可能排列。

什么是字典序？

字典序是根据其字母顺序对元素进行排列；它通常被称为字典顺序或字母顺序。就排列而言，字典序将它们按字典中单词的相同顺序排列。

• 例如，考虑集合 {A, B, C}。
• 排列按以下字典序排列：
  1. ABC
  2. ACB
  3. BAC
  4. BCA
  5. CAB
  6. CBA
• 目标是为长度为 n 的字符串生成所有可能的字符组合，并按排序顺序排列。
• 考虑以下示例以进一步理解这个问题：
  • 输入 "XYZ"
  • 输出为 XYZ, XZY, YXZ, YZX, ZXY, ZYX。
• 在这种情况下，所有排列都必须按字典序（即字母升序）打印。

排序数组是排列的初始元素；因此，解决此问题的第一步是按字母升序对其进行排序。之后，它会生成字符串的下一个更高级别的排列。

您可以查看以下代码以更好地理解解决方案：

输出

代码解释

所提供的 C++ 代码以字典序创建并输出给定字符串的每个变体。代码中使用的逻辑解释如下：

• 在排序时，使用 compare 函数比较字符。它是 C 标准库中一个常见的比较函数，可以与 qsort 一起使用。
• 在字符串中，可以使用 swap 函数交换两个字符。
• 在字符串的给定范围内，finduBound 函数首先找到比特定字符小的最右边的字符。此函数用于确定字符串中哪个字符应与位置 i 处的字符进行交换。
• 在使用 qsort 对输入文本进行排序以使其按字典序排列后，generatePermutation 函数会生成并打印每个排序排列。
• "NOPQ" 是一个输入到主函数的示例字符串。
• 主函数打印的消息表明排列将按排序顺序打印。
• 之后，调用函数 generatePermutation，传入输入文本 "NOPQ"。

在保持字典序的同时频繁生成排列是代码的基本逻辑。为了实现下一个排列，字符被交换，并且字符串始终保持有序。这个循环一直持续到生成并打印出所有可能的组合。输出显示了代码在字典序中生成给定字符串所有可能变体的良好效果。

示例程序

输出

代码解释

• 使用 std::sort，我们首先按字典序对输入字符串进行排序。
• 之后，我们使用 do-while 循环和 std::next_permutation 创建并报告排列。此函数会生成下一个排列，直到没有更多按字典序更大的排列可以形成。
• 由于第一个排序步骤，我们在循环内部输出的当前排列将按顺序排序。
• 使用输入 "XYZ"，此代码在运行时将按字典序输出可能性。