首页 > 代码库 > 小算法-计算下一个排列

小算法-计算下一个排列

2024-07-08 00:08:08   230人阅读

2 8 5 3 1

1.从后往前，找到第一个逆序的数 pivot

2.从后往前，找到第一个比pivot大的数 change

3.交换 pivot 和 change的值

4.把pivot这个位置后面的数 reverse，就是 8 5 2 1变成 1 2 5 8

最终为3 1 2 5 8

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
*  num.begin() num is a vector, it means the first element in num
*  num.end*()  num is a vecotr, it means the last element‘s next element, attention it out of num
*  reverse_iterator 按照逆序寻址元素的迭代器
*  c.rbegin() 返回一个逆序迭代器，它指向容器的最后一个元素
*  c.rend()   返回一个逆序迭代器，它指向容器的第一个元素的前面位置
*/
class Solution{
public:

bool nextPermutation(vector<int> &num)
    {
        return next_permutation(num.begin(),num.end());
    }

    template<typename BidiIt>
    bool next_permutation(BidiIt first,BidiIt last)
    {
        const auto rfirst = reverse_iterator<BidiIt>(last);
        const auto rlast = reverse_iterator<BidiIt>(first);

        auto pivot = next(rfirst);
        while(pivot != rlast && *pivot >= *prev(pivot))
        {
            ++pivot;
        }
        
        //this is the last permutation, or the next is the same as the begin one
        if(pivot == rlast)
        {
            reverse(rfirst,rlast);
            return false;
        }
        //find the first num great than pivot
        auto change = rfirst;
        while(*change<=*pivot)
            ++change;

        swap(*change,*pivot);
        reverse(rfirst,pivot);
        return true;
    }
};

int main()
{
    vector<int> num;
    num.push_back(2);
    num.push_back(8);
    num.push_back(5);
    num.push_back(3);
    num.push_back(1);
    Solution myS;
    myS.nextPermutation(num);
    //3 1 2 5 8
    return 0;
}

在这个过程中遇到了一个坑：visual C++ debug下 vector::reverse_iterator current显示是错的，也就是如果 3 1 2 5 8 ,iter指的是1的时候，debug显示的是2.

但是在文章http://www.cnblogs.com/SummerHeart/archive/2008/06/04/1213860.html 解释了这个现象，解释为特性。


联系
我们