美文网首页
C/C++全排列函数

C/C++全排列函数

作者: 我是恐龙_35b2 | 来源:发表于2019-07-15 15:47 被阅读0次

C++中有全排列函数next_permutation,前提是数据必须有序,因此先对其进行排序,再使用该函数:

vector<vector<int>> permute(vector<int>& nums)
{
      vector<vector<int>> result;
      sort(nums.begin(),nums.end());
      result.push_back(nums);
      while (next_permutation(nums.begin(), nums.end()))
      {
        result.push_back(nums);
      }
      return result;
}

全排列的深度优先(DFS)实现

//全排列的深度优先(DFS)实现
void dfs(vector<int>& nums, map<int, int>& selected, int index,vector<int>& oneresult, vector<vector<int>>&result)
{
    if (index == nums.size())                           //排列完一次
    {
        result.push_back(oneresult);                    //本次结果加入最终结果
        return;
    }
    for (int i = 0; i < nums.size(); i++)               //对所有数据进行遍历
    {
        if (selected[i] != 0)                           //若已经选择过则跳过
            continue;
        //这里使用人工方式进行回溯完全是因为函数参数使用的是引用,
        //使用引用的方式是为了减少递归中参数复制导致时间的浪费。
        selected[i] = 1;                                //添加选中标识
        oneresult.push_back(nums[i]);                   //本元素加入本次结果中
        dfs(nums, selected, index + 1, oneresult, result);  //下一次遍历
        selected[i] = 0;                                //清除选中标识
        oneresult.pop_back();                           //本元素出本次结果
    }
}

相关文章

  • C/C++全排列函数

    C++中有全排列函数next_permutation,前提是数据必须有序,因此先对其进行排序,再使用该函数: 全排...

  • 使用C++ STL的next/prev_permutation函

    使用C++ STL的next_permutation函数可以简单的枚举出一个升序排列的字符串的全排列,它包含在头文...

  • C++全排列算法

    参考:【基础算法】- 全排列 代码参考上面链接,花了一些功夫才读懂,添加了注释。 经验是:读代码时拿纸笔模拟单步执...

  • - C++ Builder

    C++ Builder 参考手册 ➙ 按功能排列的 成员• 类型转换函数•...

  • 全排列

    问题描述 求1-n的所有按字典序的全排列 C++实现

  • 花式全排列,不服不行(康拓展开)

    偶尔做了些蓝桥杯练习题,发现一题全排列,看着简单以为C++全排列库直接暴力就行,然而……答案数据高达229526多...

  • windows逆向3

    VC 程序内存和编译的一些特征C++ 构造函数C++ 成员函数C++ 析构函数C++ 全局对象的构造C++ 全局对...

  • C/C++学习资料收集

    Standard C 语言标准函数库速查,这个网址很全 Standard C++ Library Overview...

  • C/C++ 取整函数ceil(),floor()2019-10-

    转自: C/C++ 取整函数ceil(),floor() C/C++ 取整函数ceil(),floor() #in...

  • 一些函数

    cmp函数 C++ sort cmp函数 - lzz的博客 - CSDN博客 浅谈C/C++排序函数中cmp()比...

网友评论

      本文标题:C/C++全排列函数

      本文链接:https://www.haomeiwen.com/subject/oubnkctx.html