21xrx.com
2024-06-03 05:38:07 Monday
登录
文章检索 我的文章 写文章
C++全排列递归算法代码
2023-07-08 05:15:11 深夜i     --     --
C++ 全排列 递归算法 代码

全排列是指将一组元素按照一定的顺序进行排列的操作,C++递归算法代码实现全排列非常简单。

下面是C++的全排列递归算法代码:


#include <iostream>

#include <vector>

using namespace std;

void permute(vector<int>& nums, int l, int r)

{

  if (l == r) { // 输出当前排列

    for (int i = 0; i <= r; ++i)

      cout << nums[i] << " ";

    cout << endl;

    return;

  }

  for (int i = l; i <= r; ++i) { // 枚举下一个数,并以其为起点递归生成排列

    swap(nums[l], nums[i]); // 交换位置

    permute(nums, l+1, r);

    swap(nums[l], nums[i]); // 还原位置

  }

}

int main()

{

  vector<int> nums = 1; // 原始序列

  permute(nums, 0, nums.size()-1); // 调用递归函数生成排列

  return 0;

}

在上面的代码中,我们定义了一个permute函数,它的参数分别是当前排列序列nums、当前处理的子序列起始索引l和结束索引r。在permute函数中,当l==r时,输出当前排列序列即可。

当l!=r时,我们需要枚举下一个数,并以它为起点递归生成排列。因此,我们在for循环中遍历nums中从l到r的数字,并且将它们和l位置的数字交换位置,然后以这个新的nums为输入,递归调用permute函数,使之生成下一级的排列。

代码中使用了标准库中的vector和swap函数,vector是一个可变数组,swap函数可以轻易地交换数组中的两个元素,又由于C++的vector带有成员函数size,因此我们可以轻松获得nums的长度,而不必单独定义一个变量。

总体来说,C++的全排列递归算法相对其他语言的实现非常优雅、简短、易读,可以方便地完成全排列的操作。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复