Next Permutation

Given a list of integers, which denote a permutation.

Find the next permutation in ascending order.

Example

For [1,3,2,3], the next permutation is [1,3,3,2]

For [4,3,2,1], the next permutation is [1,2,3,4]

Note

The list may contains duplicate integers.

Solution

Time: O(N)
From right to left, find the first digit (num[front]) which violate the increase trend
From right to left, find the first digit (num[end] > num[front])
Swap the end and front
Reverse all digits on the right side of num[front]

(Next-Permutation.py) download

class Solution:
    # @param num :  a list of integer
    # @return : a list of integer
    def nextPermutation(self, num):
        # write your code here
        if num == None or len(num) < 2:
            return num
        end = len(num)-1
        front = end-1

        # find the element who breaks the rule
        while front>=0:
            if num[front] < num[end]:
                break
            else:
                front -= 1
                end -= 1
        if front==-1:
            num.sort()
        else:
            # find the smallest element(element>num[front])
            end = len(num)-1
            while end > front:

                if num[end] > num[front]:
                    break
                else:
                    end -= 1

            # swap the front, end   
            num[front],num[end] = num[end],num[front]
            num[front+1:] = sorted(num[front+1:])
        return num