[leetcode] permutations

permutations

• 서로다른 숫자로 구성된 배열을 입력으로 받는다
• 가능한 모든 조합의 순열을 리턴

Solution1

• itertools의 permutations를 사용

code1

from itertools import permutations

class Solution(object):
    def permute(self, nums):
        return list(map(list,permutations(nums)))

Solution2

• next_permutation(nums)메서드 구현
  1. nums[i-1] < nums[i] 인 가장 큰 i 찾기
  2. nums[i:] 범위에서 nums[i-1] < nums[j] 인 가장큰 j 찾기
  3. nums[i-1] 와 nums[j] 를 swap
  4. nums[i:] 를 양 끝에서 가운데 방향으로 swap 반복

code2

class Solution(object):
    def permute(self, nums):


        def next_permutation(nums, results):
            size = len(nums)
            i = j = size-1

            # nums[i-1] < nums[i] 인 가장 큰 i 찾기
            while i > 0 and nums[i-1] >= nums[i] : i-=1
            if i == 0 : return False # next_permutation impossible

            # nums[i:] 에서 nums[i-1] 보다 큰 nums[j] 중 가장큰 j 찾기
            while nums[i-1] >= nums[j] : j-= 1

            # nums[i-1]과 nums[j] 를 swap
            nums[i-1], nums[j] = nums[j], nums[i-1]

            # nums[i:] 를 양끝 에서 부터 swap
            start,end = i, size-1
            while start < end:
                nums[start],nums[end]=nums[end],nums[start]
                start,end = start+1, end-1
            results.append(nums[:])
            return True

        nums.sort()
        results=[nums[:]]
        while next_permutation(nums,results):pass
        return results

Solution3

• dfs를 이용 dfs(selected:list, remain:set)
• 종료조건 : selected 길이가 len(nums) or remain 개수가 0

code3

class Solution(object):

    def permute(self, nums):
        results = []

        def dfs(selected, remain):
            if not len(remain):
                results.append(selected[:])
                return

            
            for el in remain:
                selected.append(el)
                dfs(selected, remain-{el})
                selected.pop()

        nums_set = set(nums)
        dfs([], nums_set)
        return results