next permutation.

https://leetcode.com/problems/next-permutation/discuss/13867/C%2B%2B-from-Wikipedia

의 댓글에 아주 잘 설명되어있다. 정리함.

next permutation을 구하는 방법.

2,3,6,5,4,1로 알고리즘의 예를 듬.

1. 오른쪽에서 왼쪽으로 순회하면서 수가 증가하지 않는 부분을 찾는다. 2,3,6,5,4,1에서는 3 이다.

2-1. 수가 증가하지 않는 부분이 없으면 이 뜻은 permutation의 맨 마지막이라는 뜻이다. 이경우 맨 마지막의 다음은 맨 처음이므로 그냥 순서를 거꾸로 해주면 된다. 예로 6,5,4,3,2,1의 경우인데, 이 경우 그냥 거꾸로 순서를 해주면 맨 처음인1,2,3,4,5,6이다.

2-2. 수가 증가하지 않는 부분을 찾았으면 다시 맨 오른쪽에서부터 왼쪽으로 가면서 증가하지 않는 숫자인 3보다 큰 수를 찾는다. 2,3,6,5,4,1의 경우에는 4 이다. 그후 3과 4의 위치를 바꿔준다. 그러면 2,4,6,5,3,1이 되는데,

이제 마지막으로 4 오른쪽에 있는 수들을 전부 순서를 거꾸로 바꿔준다. 그러면 2,4,1,3,5,6이 나오는데 이게 next permutation이다.

leetcode 31 https://leetcode.com/problems/next-permutation/ 의 푸는 코드를 가져옴.

class Solution(object):
    def nextPermutation(self, nums):
        change_index = -1
        for i in xrange(len(nums)-1, 0, -1):  # 1번 파트.
            if nums[i] > nums[i-1]:
                change_index = i-1
                break
        if change_index == -1:  # 2-1번 파트.
            nums[:] = nums[::-1]
            return
        
        #print nums
        for i in xrange(len(nums)-1, -1, -1):  # 2-2번 파트.
            if nums[i] > nums[change_index]:
                nums[change_index], nums[i] = nums[i], nums[change_index]
                nums[:] = nums[:change_index+1] + nums[change_index+1:][::-1]
                return

시간복잡도는 O(n)