31.Next Permutation

31.Next Permutation My Submissions
Question
Total Acceepted: 54346 
Total Submissions: 21212155 
Difficulty: Medium
Implement next permutation、which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible、it must rearrange it as the lowest possible order(ie、sorted in ascending order)
The replace ment must be in-place,do not allocate extra memory.
Here are some examples.Inputare in the left-hand column and its coresolding outputare in the right-hand column.1,2,3 →  1,3,2 3,2,1 →  1,2,3 1,1,5 →  1,5,1Subscribe to see which companies asked this question
ハイドTags
 
Aray
Hide Simiar Probles
 
(M)Permutations (M)Permutations II (M)Permutation Sequence (M)Palindrome Permutation II
STLで作って、秒で殺す

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

この問題はあまり面白くないと思います.早く規則を考え出しにくいです.
しかし、明らかな法則は:
1、昇順は最小の組み合わせで、降順は最大の組み合わせです.
2,ある数の次の数は彼より大きい最小の組み合わせ数です.例えば123、次の彼より大きい最小の組み合わせは132です.下位から処理しなければなりません.
3,stlの処理は、下位(配列の最後)から始まり、最初の昇順シーケンスを見つけて交換し、後の数を逆にすることです.例えば、123123123311は1243311であり(最初の昇順はすでに交換されている)、明らかにこの数は最小ではなく、後の数を逆にした後が最小である1243311は1243113である.そ、done

//    （      ）：
//  ：abc,acb,bac,bca,cab,cba，       ，              ，                ，   ，           
//  stl    
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.empty() || nums.size()==1)
            return;
        if(nums.size()==2)//             ，   ......
        {    
            reverse(nums.begin(), nums.end());  
            return;
        }
        vector<int>::iterator ite1=nums.end()-1;
        for(;;)
        {
            vector<int>::iterator ite2=ite1;
            ite1--;
            if(*ite1 < *ite2)
            {
                vector<int>::iterator itej=nums.end();
                while(!(*ite1 < *--itej));
                iter_swap(ite1,itej);//  ，           ，         ，swap       
                reverse(ite2,nums.end());
                return;
            }
            
            if(ite1==nums.begin())
            { 
               reverse(nums.begin(),nums.end());
               return;
            }
        }
    }
};

注:このブログはEbowTangのオリジナルです.その後も引き続き本文を更新します.転載する場合は、必ず本条情報をコピーしてください.
原文の住所:http://blog.csdn.net/ebowtang/article/details/50450861
作者のブログ:http://blog.csdn.net/ebowtang
参考資源
【1】侯捷、《STLソースの剥析》