[파이썬 알고리즘] 18. 순열

1. 문제 leetcode 46. Permutations

 서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라.

 

2. DFS를 이용한 풀이

 이 문제는 재귀 dfs로 그래프를 탐색하여 풀 수 있다. 그래프는 []을 루트 노드로, [1,2,3], [2,1,3] 등 각 순열을 리프 노드로 삼고, 중간의 노드는 각 순열이 만들어지는 과정([1,2] 등)으로 가진다. DFS 함수의 인자로는 지금까지 만들어진 순열을 넣는 path, path에 아직 순열에 추가되지 않은 candidates를 준다. 주어진 수를 모두 순열에 사용해서 candidates가 남아있지 않다면, 지금까지 만든 순열인 path를 결과에 추가한다. 만약 순열 path에 추가할 candidates가 남아 있다면 남아있는 숫자를 모두 넣어서 DFS 자신을 호출한다.

 

 여기서 중요한 점은 재귀함수를 호출할 때 인자로 변수가 아니라 값을 넘겨주어야 한다는 점이다. 예를 들어서 아래 코드에서 재귀호출시 candidates 값을 넘겨줄 때를 살펴보자. 지금은 candidates[:i]+candidates[i+1:]의 형태로 값만을 넘겨주고 있다. 하지만 candidates 값 자체를 먼저 변경하고, 함수에 인자로 candidates를 넘겨준다면 어떤 일이 일어날까? 재귀호출된 dfs에서 candidates의 값을 바꾸는 경우, 원래 함수에서의 candidates 값도 영향을 받게 된다. 따라서 지금의 path, candidates를 인자로 전달하는 방식처럼 값만을 전달해야 한다. 

def permute(self, nums: List[int]) -> List[List[int]]:
    res = []

    def dfs(candidates, path):
        if not candidates:
            res.append(path)
            return # backtracking
        for i in range(len(candidates)):
            dfs(candidates[:i]+candidates[i+1:], path+[candidates[i]])
        return

    dfs(nums, [])
    return res

 

3. itertools 모듈 사용

 다른 방법은 파이썬의 모듈을 사용하는 것이다. iteratools라는 모듈은 주어진 데이터에서 순열, 조합을 뽑아내는 기능을 가진다. 이 모듈을 사용해서 아주 간단하게 풀 수도 있다.

def permute(self, nums: List[int]) -> List[List[int]]:
    return list(itertools.permutations(nums))