LeetCode: Next Permutation

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 replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

---

There are four steps to solve this problem:

1. Find the largest element index that num[index] < num[index+1].

2. If there doesn't exist such index, then the list will be in descending order. Reverse the whole list.

3. Find the largest element index' that num[index'] > num[index] and swap them.

4. Reverse the list from index+1 to the end.

C++ Code:

/*
 * func: next_permutation
 * goal: get the next permutation of numbers which is lexicographically next greater one
 * @param num: the vector of numbers
 * return:
 */
void next_permutation(vector<int> &num){
    if(num.size() <= 1){
        return;
    }
    //Start from the end, find the largest index where num[index] < num[index + 1]
    int index = static_cast<int>(num.size()-2);
    while(index >= 0){
        if(num[index] >= num[index+1]){
            --index;
        }else{
            break;
        }
    }
    
    //If there doesn't exist that i, reverse the whole vector
    if(index < 0){
        reverse(num.begin(), num.end());
    }else{
        //Find the largest index' where num[index'] > num[index]
        int index_g = static_cast<int>(num.size()-1);
        while(index_g > index){
            if(num[index_g] > num[index]){
                break;
            }else{
                --index_g;
            }
        }
        //Swap num[index'] and num[index]
        swap(num[index_g], num[index]);
        
        //Reverse from index+1 to the end
        reverse(num.begin()+index+1, num.end());
    }
}

Python Code:

# func: Implement next permutation, which rearranges numbers into the
#       lexicographically next greater permutation of numbers.
# @param num: input number list
# @return: return next permutation
def next_permutation(num):
    if len(num) <= 1:
        return num

    #Find the largest index where num[index] < num[index+1]
    index = len(num)-2
    while index >= 0:
        if num[index] < num[index+1]:
            break
        else:
            index -= 1

    #If there doesn't exist that index, reverse the whole list
    if index < 0:
        return num[::-1]

    #Find the largest index' that num[index'] > num[index]
    index_g = len(num)-1
    while index_g > index:
        if num[index_g] > num[index]:
            break
        else:
            index_g -= 1

    #Swap index_g and index
    tmp = num[index]
    num[index] = num[index_g]
    num[index_g] = tmp

    #Reverse from index + 1 to the end
    num[index+1:] = reversed(num[index+1:])

    return num