看了水中的鱼的解题报告。Find a solution here.

1. From right to left, find the first digit (PartitionNumber) which violates the increase trend.

2. From right to left, find the first digit which is larger than PartitionNumber, call it ChangeNumber.

3. Swap PartitionNumber and ChangeNumber.

4. Reverse all the digit on the right of partition index.

class Solution:
    # @param num, a list of integer
    # @return a list of integer
    def nextPermutation(self, num):
        lenNum = len(num)
        # find the first number (PartitionNumber) which violates the increase trend
        partitionIndex = -1
        for i in reversed(xrange(lenNum - 1)):
            if num[i] < num[i + 1]:
                partitionIndex = i
                break
        if partitionIndex != -1:
            for i in reversed(xrange(lenNum)):
                if num[i] > num[partitionIndex]:
                    num[i], num[partitionIndex] = num[partitionIndex], num[i]
                    break
        # reverse all numbers behind PartitionIndex
        i = partitionIndex + 1
        j = lenNum - 1
        while i < j:
            num[i], num[j] = num[j], num[i]
            i += 1
            j -= 1
        return num