博客

next_permutation函数的功能是将数组中选定范围的数按照字典序进行全排列。


基本用法如下：

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int a[5]={2,5,1,3,8};
	sort(a,a+5);//如果不排序则从当前状态开始进行全排列  
	do
	{
		for(int i=0;i<5;i++)
		cout<<a[i]<<" ";
		cout<<endl; 
	}while(next_permutation(a,a+5));
	 //(a+m，a+n)指从数组下表为m到n-1的数进行全排列 
	 return 0;
}

底层实现：

lc31. 下一个排列

//从后往前找第一对相邻的非递减序列
//将左边的数与右边递减序列中第一个大于它的数进行交换

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size()==1) return;
        bool flag = false;
        for(int i =1;i<nums.size();i++)
        {
            if(nums[i]>nums[i-1]) 
            {
                flag =true;
                break;
            }

        }
        if(flag==false) 
        {
            reverse(nums.begin(),nums.end());
            return;
        }

        for(int i=nums.size()-2;i>=0;i--)
        {
            if(nums[i]<nums[i+1]) 
            {
                for(int j=nums.size()-1;j>i;j--)
                {
                    if(nums[j]>nums[i]) 
                    {
                        swap(nums[i],nums[j]);
                        reverse(nums.begin()+i+1,nums.end());
                        return;
                    }
                }
            }
        }
    }
};