Permutation-白红宇

Permutation

阅读量：795 次

发布时间：2023-02-27

本文共 2202 字，大约阅读时间需要 7 分钟。

要解决生成所有可能排列的问题，我们可以使用C++ STL中的next_permutation函数。以下是实现步骤：

方法一：使用STL的`next_permutation`函数

包含必要的头文件：

包含vector和algorithm头文件。

定义命名空间：

在代码中使用namespace ns {来定义命名空间。

实现next_permutation仿射函数：

这个函数接收两个双向迭代器，返回是否能生成下一个排列。

递减地找到最后一个元素，检查是否需要交换。

如果前一个排列，返回false。

创建解决方案类：

定义一个Solution类。

包含一个permute方法，该方法接受一个向量作为输入。

对输入向量进行排序。

初始化一个空结果向量。

使用do-while循环，调用next_permutation函数，直到无法生成下一个排列。

每次循环中，将当前排列添加到结果向量中。

主函数：

初始化一个向量v，包含需要排列的数字。

创建一个Solution对象。

调用permute方法，获取所有排列。

输出结果。

方法二：递归实现

包含必要的头文件：

包含vector、algorithm和iostream头文件。

定义递归函数：

定义一个dfs递归函数，用于生成所有排列。

递归终止条件是当前向量大小等于输入向量大小。

对于每个元素，检查是否已经存在于当前向量中，如果不存在，则将其添加到当前向量，并调用递归。

实现permute方法：

对输入向量进行排序。

初始化一个空结果向量。

调用dfs函数，生成所有排列，并将其添加到结果向量中。

主函数：

初始化向量v，包含需要排列的数字。

创建一个Solution对象。

调用permute方法，获取所有排列。

遍历结果向量，输出每个排列。

代码示例

#include 
   
    #include 
    
     #include 
     
      using std::vector;using namespace std;namespace ns {    template 
      
           bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) {        if (first == last) return false;        BidirectionalIterator i = last;        if (--i == first) return false;        while (i != first) {            auto t = i;            --i;            if (*i < *t) {                auto j = last;                while (!(*--j > *i)) ;                iter_swap(i, j);                reverse(t, last);                return true;            }        }        reverse(first, last);        return false;    }    class Solution {    public:        vector
       
         permute(vector
        
         & nums) { sort(nums.begin(), nums.end()); vector
         
           res; do { res.push_back(nums); } while (next_permutation(nums.begin(), nums.end())); return res; } }; int main() { vector
          
            v{1,2,3}; vector
           
             res; Solution s; res = s.permute(v); for (int i = 0; i < res.size(); ++i) { for (int j : res[i]) { cout << j; if (!j || j == 3) cout << endl; } } return 0; }}