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

C++递归实现全排列

2023-07-07 00:25:58 深夜i -- --

C++ 递归全排列实现

全排列是指对于给定的n个数，将它们进行全排列，即所有可能的排列情况。在C++中，我们可以使用递归算法来实现全排列。

递归实现全排列的基本思路是：将n个数分成两部分，第一部分为第一个数，第二部分为剩余的n-1个数，然后递归求后n-1个数的全排列，最后再将第一个数与后面的n-1个数交换位置，再将其余n-1个数递归全排列，以此类推，直到最后一个数与倒数第二个数交换位置为止，此时得到一组排列。

下面是C++递归实现全排列的代码示例：


#include <iostream>
using namespace std;
void permutation(int* nums, int start, int end) {
  if (start == end) {
    //输出一组排列
    for (int i = 0; i <= end; i++) {
      cout << nums[i] << " ";
    }
    cout << endl;
  }
  else {
    for (int i = start; i <= end; i++) {
      //将nums[i]与nums[start]交换位置
      swap(nums[i], nums[start]);
      //递归求后面n-1个数的全排列
      permutation(nums, start + 1, end);
      //还原nums[i]和nums[start]的位置
      swap(nums[i], nums[start]);
    }
  }
}
int main() {
  int nums[] = 3 ;
  int size = sizeof(nums) / sizeof(int);
  permutation(nums, 0, size - 1);
  return 0;
}

在这段代码中，我们使用了递归函数permutation来实现全排列。该函数接受三个参数：nums表示要全排列的数组，start表示要开始排列的位置，end表示要排列的最后一个位置。当start等于end时，表示已经排列完所有的数，输出该组排列即可。当start小于end时，表示还有数没有排列，将nums[i]与nums[start]交换位置，递归求后面n-1个数的全排列，最后还原nums[i]和nums[start]的位置，重复执行，直到start等于end为止。

运行上述代码，我们可以得到1,2,3的全排列：

1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2

以上就是使用C++递归实现全排列的方法及其代码示例。通过这种方法，我们可以得到一个数列中所有可能的排列，可以在很多算法问题中使用。

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

下一篇: C++中如何定义数组？

评论区

()

相似文章