下一个排列

    void nextPermutation(vector<int> &num) {
        int n=num.size();
        if(n<2)return ;
        int index=n-1;
        int k;
        while(index>=0){
            if(num[index]>num[index-1]) break;
            index--;
        }
        if(index==0){
            sort(num.begin(),num.end());
            return ;
        }
        int j=n-1;
        while(j>=index){
            if(num[j]>num[index-1]) break;
            j--;
        }
        swap(num[j],num[index-1]);
        sort(num.begin()+index,num.end());
    }

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if(num.size()<=1) return;
        int i = num.size()-1;
        while(i>0 && num[i]<=num[i-1]) --i;
        if(i==0) {                           //5,4,3,2,1
            reverse(num.begin(),num.end());
        }else{
            int j = num.size()-1;
            while(num[j]<=num[i-1]) --j;
            swap(num[j],num[i-1]);
            reverse(num.begin()+i,num.end());
        }
    }
};

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        next_permutation(num.begin(), num.end());
    }
};

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if(num.empty())
            return;
        int n=num.size();
        int i=n-1;
        while(i>=1){
            if(num[i]>num[i-1]){
                
                break;
            }
            i--;
        }
        if(i<1){
            int begin=0,end=n-1;
            while(begin<end){
                int tmp=num[begin];
                num[begin]=num[end];
                num[end]=tmp;
                begin++;
                end--;
            }
        }
        else{
            int begin=i,end=n-1;
            while(begin<end){
                int tmp=num[begin];
                num[begin]=num[end];
                num[end]=tmp;
                begin++;
                end--;
            }
            int j=i;
            while(j<n&&num[j]<=num[i-1])
                j++;
            int tmp=num[i-1];
            num[i-1]=num[j];
            num[j]=tmp;
        }
    }
};

思路：
首先从后前查找第一个满足i-1<i的位置i，如果找不到，说明这个排列是降序的，那么返回所有数的顺序排列；
否则，说明i及以后的排列是降序的，首先将该部分置换为升序的，然后从中找比i-1位置处的值大的最小的那个数，
然后将i-1位置处的数与找到的数进行交换即可。

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if(num.size() <= 1) {
            return;
        }
        int j, tmp;
        for(int i = num.size()-1; i>=1; i--) {
            if(num[i] > num[i-1]) {
                j = i;
                while(num[j] > num[i-1] && j < num.size()) {
                    j++;
                }
                j--;
                tmp = num[i-1];
                num[i-1] = num[j];
                num[j] = tmp;
                sort(num.begin()+i, num.end());
                return;
            }
        }
        sort(num.begin(), num.end());
        return;
    }
};

/***
Find the largest index k such that nums[k] < nums[k + 1]. If no such index exists, just reverse nums and done.
Find the largest index l > k such that nums[k] < nums[l].
Swap nums[k] and nums[l].
Reverse the sub-array nums[k + 1:].
***/

class Solution
{
public:
    void nextPermutation(vector<int>& nums)
    {
        int n = nums.size(), k, l;
        if(n < 1) return ;
        for(k = n - 2; k >= 0; --k)
        {
            if(nums[k] < nums[k + 1])
                break;
        }
        if(k < 0)
            reverse(nums.begin(), nums.end());
        else
        {
            for(l = n - 1; l > k; --l)
            {
                if(nums[k] < nums[l])
                    break;
            }
            swap(nums[k], nums[l]);
            reverse(nums.begin() + k + 1, nums.end());
        }
    }
};

// next_permutation的使用

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size() == 0)
            return ;
        if(next_permutation(nums.begin(), nums.end()))
        {

        }
        else{
            sort(nums.begin(), nums.end());
        }
    }
};

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if(num.size() <= 1) return;
        int i = num.size()-1,j = num.size()-1;
        while(i > 0 && num[i] <= num[i-1]) --i;
        if(i){
            while(i > 0 && num[j] <= num[i-1]) --j;
            swap(num[j],num[i-1]);
        }
        reverse(num.begin() + i,num.end());
    }
};

class Solution {
    public:
    // 字典序问题，非常简单
    void nextPermutation(vector<int>& nums) {
        if (nums.empty())
            return;
        bool isMax = true;
        vector<int>::iterator it1, it2;
        for (auto it = nums.end() - 2; it != nums.begin() - 1; --it) {
            if (*it < *(it + 1)) {
                it1 = it;
                isMax = false;
                break;
            }
        }
        if (!isMax) {
            for (auto it = nums.end() - 1; it != nums.begin() - 1; --it) {
                if (*it > *it1) {
                    it2 = it;
                    swap(*it1, *it2);
                    sort(it1 + 1, nums.end());
                    break;
                }
            }
        }
        else
            reverse(nums.begin(), nums.end());
    }
};

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int l=num.size();
        int left=0,right=0,tmp=0;
        int i;
        for(i=0;i<l-1;++i){
            if(num[i]<num[i+1]){
                left=i;
                right=i+1;
            }
            else if(num[i]>num[left] && num[i]<num[right]) right=i;
        }
        if(num[i]>num[left] && num[i]<num[right]) right=i;
        if(left==0 && right==0) sort(num.begin(),num.end());
        else{
            swap(num[left],num[right]);
            sort(num.begin()+left+1,num.end());
        }
    }
};

Well, in fact the problem of next permutation has been studied long ago. From the Wikipedia page, in the 14th century, a man named Narayana Pandita gives the following classic and yet quite simple algorithm (with minor modifications in notations to fit the problem statement):

1. Find the largest index k such that nums[k] < nums[k + 1]. If no such index exists, the permutation is sorted in descending order, just reverse it to ascending order and we are done. For example, the next permutation of [3, 2, 1] is [1, 2, 3].
2. Find the largest index l greater than k such that nums[k] < nums[l].
3. Swap the value of nums[k] with that of nums[l].
4. Reverse the sequence from nums[k + 1] up to and including the final element nums[nums.size() - 1].

Quite simple, yeah? Now comes the following code, which is barely a translation.

Well, a final note here, the above algorithm is indeed powerful --- it can handle the cases of duplicates! If you have tried the problems Permutations and Permutations II, then the following function is also useful. Both of Permutations and Permutations II can be solved easily using this function. Hints: sort nums in ascending order, add it to the result of all permutations and then repeatedly generate the next permutation and add it ... until we get back to the original sorted condition. If you want to learn more, please visit this solution and that solution.

class Solution { void nextPermutation(vector<int>& nums) { int k = -1; for (int i = nums.size() - 2; i >= 0; i--) { if (nums[i] < nums[i + 1]) {
    			k = i; break;
    		}
    	} if (k == -1) {
    	    reverse(nums.begin(), nums.end()); return;
    	} int l = -1; for (int i = nums.size() - 1; i > k; i--) { if (nums[i] > nums[k]) {
    			l = i; break;
    		} 
    	} 
    	swap(nums[k], nums[l]);
    	reverse(nums.begin() + k + 1, nums.end()); 
    }
};

import java.util.Arrays;
public class Solution {
    public void nextPermutation(int[] num) {
        if (num==null || num.length==0)
            return;
        //从后向前找一个位置i满足num[pos] > num[pos-1]
        int len = num.length;
        int pos = Integer.MAX_VALUE;
        for (int i=len-1; i>=1; i--) {
            if (num[i] > num[i-1]) {
                pos = i;
                break;
            }
        }
        if (pos == Integer.MAX_VALUE) {
            Arrays.sort(num);
            return ;
        }
        //从pos开始，将后面的变为升序排列
        Arrays.sort(num, pos, len);
        //从pos开始，找到第一个比num[pos-1]大的数
        for (int i=pos; i<len; i++) {
            if (num[i] > num[pos-1]) {//找到了
                //交换两个位置的元素
                int temp = num[pos-1];
                num[pos-1] = num[i];
                num[i] = temp;
                return;
            }
        }//for
    }
}

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int n = num.size();
        if(n == 0)
        	return;
        int i,flag=0;
        for(i=n-1;i>0;i--)
        	if(num[i] > num[i-1])
        	{
        		flag = 1;
        		break;
			}
		
		if(flag == 0)
			sort(num.begin(),num.end());
		else{
			for(int j=n-1;j>=i;j--)
				if(num[j] > num[i-1])
				{
					swap(num[j],num[i-1]);
					break;
				}
			sort(num.begin()+i,num.end());
		}
    }
};

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if(num.size()==0) return ;
        int i,N=num.size(),flag=0,j;
        for(i=N-1;i>0;i--)
            if(num[i]>num[i-1])
            {
            	flag=1;
            	break;
        	}
        if(flag==0)
            sort(num.begin(),num.end());
        else
        {
        	for(j=N-1;j>=i;j--)
                if(num[j]>num[i-1])
                {
                	swap(num[j],num[i-1]);
                	break;
            	}
            sort(num.begin()+i,num.end());
        }
    }
    void swap(int &a,int &b)
    {
        int temp;
        temp=a;
        a=b;
        b=temp;
    }
};

    /*
    * 目的：下一个排列
    * 方法：
    * 例如：1 2 3 7 6 5 1
    * 1.从后往前找到不满足递增排序的点
    * 2.如果不存在这样的点证明数组是非递增的，直接reverse，然后返回即可
    * 3.如果找到，例如上例中的7，则重新从后往前寻找大于3的第一个数，即5
    * 4.交换3和5的位置，然后将后面的数组升序排列，即可得到结果
    */
    void nextPermutation(vector<int> &num) {
        if (num.size()<=1)return;
        int i = num.size()-1;
        while(i>0&& num[i]<=num[i-1])
            i--;
        if (i==0)
            reverse(num.begin(),num.end());
        else{
            int j = num.size()-1;
            while(num[j]<=num[i-1])
                j--;
            swap(num[i-1],num[j]);
            sort(num.begin()+i,num.end());
        }
    }

public void nextPermutation(int[] num) {
        if(num == null || num.length <= 1)
            return;
        
        int length = num.length;
        
        int markIndex = length - 1;
        //找不满足递增的点
        while(markIndex > 0 && num[markIndex] <= num[markIndex-1]){
            markIndex--;
        }
        //无递增，代表是全排列第一个输出
        if(markIndex == 0){
            reverse(num);
        }else{
            int j = num.length - 1;
            //找到大于乱序点前一个数的第一个数
            while(num[j] <= num[markIndex-1]){
                j--;
            }
            //交换两数
            swap(num,markIndex-1,j);
            //对交换后乱序点之后的数进行排序，这里是length，因为左闭右开
            Arrays.sort(num,markIndex,length);
        }
    }
    
    public void reverse(int[] num){
        int length = num.length;
        int tmp = 0;
        for(int i = 0 ; i < length/2 ; i++){
            tmp = num[i];
            num[i] = num[length - i - 1];
            num[length - i - 1] = tmp;
        }
    }
    
    public void swap(int[] num,int i,int j){
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }

import java.util.*;
public class Solution {
    public void nextPermutation(int[] nums) {
        if (nums.length <= 1) {
			return;
		}

		// 从右往左找，相邻的两个增序位置，用 a,b记录
		int a = -1,b = -1,c = -1;
		for (int j = nums.length - 1; j >= 1; j--) {
			if (nums[j] > nums[j - 1]) {
				a = j - 1;
				b = j;
				break;
			}
			// 如果 j == 1,代表整个数组都是降序的，直接返回升序
			if (j == 1) {
				Arrays.sort(nums);
				return;
			}
		}

		// 从 end到b 最小的一个比a大的数
		boolean flag = false;
		for(int j = nums.length - 1; j > a; j--) {
			if (nums[j] > nums[a] && !flag) {
				nums[j] = nums[j] ^ nums[a];
				nums[a] = nums[j] ^ nums[a];
				nums[j] = nums[j] ^ nums[a];
				flag = true;
				continue;
			}
			if (nums[j] < nums[a] && flag) {
				nums[j] = nums[j] ^ nums[a];
				nums[a] = nums[j] ^ nums[a];
				nums[j] = nums[j] ^ nums[a];
			}
		}
		Arrays.sort(nums,b,nums.length);
    }
}

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if(num.size()==1 || num.size()==0)
            return;
        int i=num.size()-2;
        while(i>=0 && num[i]>=num[i+1]) i--;
        if(i==-1){ //说明从后往前非递减
            sort(num.begin(),num.end());
            return;
        }
        int j=num.size()-1;
        while(j>i && num[j]<=num[i]) j--;
        swap(num[i],num[j]);
        reverse(num.begin()+i+1,num.end());
    }
};