31. Next Permutation.py

class Solution(object):
    def nextPermutation(self, nums):
        size = len(nums)
        ti = size - 2

        while ti >= 0:
            if nums[ti] < nums[ti+1]:
                break
            ti -= 1

        if ti >= 0:
            ni = size - 1
            while ni > ti:
                if nums[ni] > nums[ti]:
                    break
                ni -= 1

            nums[ti], nums[ni] = nums[ni], nums[ti]

            half = (size - 1 - ti) / 2
            for i in range(0, half):
                nums[ti + i + 1], nums[size - 1 - i] = nums[size - 1 - i], nums[ti + i + 1]
        else:
            half = size / 2
            for i in range(0, half):
                nums[i], nums[size - 1 - i] = nums[size - 1 - i], nums[i]



if __name__ == "__main__":
    s = Solution()
    a = [100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
    s.nextPermutation(a)
    print(a)