C++递归实现全排列算法 |21xrx.com

C++递归实现全排列算法

2023-07-12 19:34:09 深夜i -- --

- C++ - 递归 - 全排列 - 算法

全排列是一种非常常见的算法，它用于将一组数据按照一定的顺序进行排序。在 C++ 中，我们可以使用递归方式来实现全排列算法，以下是该算法的实现过程。

首先我们需要先了解什么是全排列。全排列指的是将一组数按照一定的顺序进行排序，使其每一个数都参与了一次排序，并且和其他数一起组成了不同的排列方式。举个例子，对于 1,2,3 这三个数来说，它们的全排列有 6 种，分别是 123、132、213、231、312、321。

接下来，我们来看一下如何使用递归方式来实现全排列。

实现

我们可以将全排列的过程分为两部分：第一部分是选择排列的第一个元素，第二部分是对剩余的元素进行全排列。

如下是全排列算法的递归实现：


void permutation(string str, int begin, int end) {
  if (begin >= end)
    cout << str << endl;
    return;
  
  for (int i = begin; i < end; i++) {
    swap(str[begin], str[i]); // 选择排列的第一个元素
    permutation(str, begin + 1, end); // 对剩余的元素进行全排列
    swap(str[begin], str[i]);
  }
}

这里的 permutation 函数中，str 是输入的字符串，begin 是选择排列的第一个元素的下标，end 是字符串的长度。如果 begin >= end，说明已经找到一种排列方式，输出该排列即可。

然后，我们使用 for 循环来枚举 begin 到 end - 1 中的每一个元素，将其与 begin 元素进行交换。然后，对剩下的元素进行全排列（即递归调用 permutation 函数）。排列完成之后，还需要将两个交换过的元素再次交换位置，以便进行下一轮排列。

测试

我们可以使用如下的代码对我们实现的全排列算法进行测试：


int main() {
  string str = "123";
  permutation(str, 0, str.size());
  return 0;
}

这里我们设置的字符串为 123，然后调用 permutation 函数进行全排列，输出该字符串的所有排列。

运行程序后，可以得到如下的输出结果：

123 132 213 231 321 312

可见，我们的全排列算法已经成功实现。

总结

本篇文章介绍了如何使用递归方式来实现全排列算法。全排列算法的关键在于选择排列的第一个元素，以及对剩余元素的全排列。通过递归来实现，可以使算法更加简洁明了。

上一篇: idea打包java可执行jar包

下一篇: C++输出数字的位数

评论区

()

相似文章