【LeetCode】数组排列问题（permutations）（附加next

描述

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]

Output:

[

  [1,2,3],

  [1,3,2],

  [2,1,3],

  [2,3,1],

  [3,1,2],

  [3,2,1]

]

思路一：递归

利用STL的函数swap()来交换数组的元素

class Solution {

public:

    vector<vector<int>> permute(vector<int>& nums) {

        vector<vector<int>> ans;

        backtracing(nums, , ans);

        return ans;

    }

    void backtracing(vector<int>& nums, int begin,vector<vector<int>>& res){

        if(begin>=nums.size()){

            res.push_back(nums);

            return;

        }

        for(int i =begin;i<nums.size();++i){

            swap(nums[begin], nums[i]);

            backtracing(nums, begin + , res);

            swap(nums[begin], nums[i]);

        }

    }

};

思路二 next_permutation方法

利用STL的库函数： next_permutation 取得下一个排列

需要#include <algorithm>

class Solution {

public:

    vector<vector<int>> permute(vector<int>& num) {

        vector<vector<int> > ans;

        sort(num.begin(), num.end());

        ans.push_back(num);

        while(next_permutation(num.begin(), num.end())) //求出下一个排列组合

            ans.push_back(num);

        return ans;

    }

};

附加：next_permutation解析

在STL中，除了next_permutation外，还有一个函数prev_permutation，两者都是用来计算排列组合的函数。前者是求出下一个排列组合，而后者是求出上一个排列组合。所谓“下一个”和“上一个”，例如：对序列 {a, b, c}，每一个元素都比后面的小，按照字典序列，固定a之后，a比bc都小，c比b大，它的下一个序列即为{a, c, b}，而{a, c, b}的上一个序列即为{a, b, c}，同理可以推出所有的六个序列为：{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a}，其中{a, b, c}没有上一个元素，{c, b, a}没有下一个元素。

next_permutation的函数原型如下：

template<class BidirectionalIterator>

bool next_permutation(

      BidirectionalIterator _First,

      BidirectionalIterator _Last

);

template<class BidirectionalIterator, class BinaryPredicate>

bool next_permutation(

      BidirectionalIterator _First,

      BidirectionalIterator _Last,

      BinaryPredicate _Comp

 );

对于第二个重载函数的第三个参数，默认比较顺序为小于。如果找到下一个序列，则返回真，否则返回假。

函数实现原理如下：

　　在当前序列中，从尾端往前寻找两个相邻元素，前一个记为*i，后一个记为*ii，并且满足*i < *ii。

　　然后再从尾端寻找另一个元素*j，如果满足*i < *j，即将第i个元素与第j个元素对调，并将第ii个元素之后（包括ii）的所有元素颠倒排序，即求出下一个序列了。

　　如果*i>=j, j--，直到*i < *j。因为目的是将i处较小元素与j处仅比i处元素大的调换,比如下面：

12345==>12354,之后，然后执行next_permutation，经过for循环，i在前ii在后，ii要比i大，从后遍历，这时i=3，ii=5，j=4，所以i和j调换，成为12453，然后ii后的元素进行reverse，得到：12435，所以：

12354的后一个元素是12435.

template<class BidirectionalIterator>

bool next_permutation(

      BidirectionalIterator first,

      BidirectionalIterator last

)

{

    if(first == last)

        return false; //空序列  

    BidirectionalIterator i = first;

    ++i;

    if(i == last)

        return false;  //一个元素，没有下一个序列了  

    i = last;

    --i;  

    for(;;) {

        BidirectionalIterator ii = i;

        --i;

        if(*i < *ii) {

            BidirectionalIterator j = lase;

            while(!(*i < *--j));  

            iter_swap(i, j);

            reverse(ii, last);

            return true;

        }  

        if(i == first) {

            reverse(first, last);  //全逆向，即为最小字典序列，如cba变为abc

            return false;

        }

    }  

}

prev_permutation实现类似，就是反向查找

小结

　　用next_permutation和prev_permutation求排列组合很方便，但是要记得包含头文件#include <algorithm>。

　　虽然最后一个排列没有下一个排列，用next_permutation会返回false，但是使用了这个方法后，序列会变成字典序列的第一个，如cba变成abc。prev_permutation同理。

巴特西

【LeetCode】数组排列问题（permutations）（附加next_permutation解析）

描述

思路一：递归

思路二 next_permutation方法

附加：next_permutation解析

最新文章

热门文章