Next Permutation

 by anniekim

Processes: Take A = {1,3,2} as an example:
1. Traverse from back to forth, find the turning point, that is A[i] = 3.
2. Sort from the turning point to the end (A[i] to A[end]), so {3,2} becomes {2,3}.
3. If i equals to 0, finish! Else, goto 4.
4. Let j = i, search from A[j] to A[end] to find the first elem which is larger than A[i-1], '2' here.
5. Swap the elem A[j] with A[i-1].
Finally, the next permutation is {2,1,3}.

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