[Python] Leetcode 46. permutations
Leetcode 46 permutations
문제
서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라
입력
arr = [1,2,3]
출력
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
풀이
- 파이썬에 내장된 itertools 패키지의 combinations 모듈과 permutations 모듈을 통해 손쉽게 순열과 조합을 구할 수 있다.
- itertools 모듈을 쓰지 못하는 경우 재귀를 통해 구현할 수 있으나 막상 짜보니 어려워 정리해보려고 한다.
- 조합의 경우는 start 패러미터를 추가로 받는다. (중복을 제거하기 위해)
# 순열
# 서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라
arr = [1, 2, 3]
n = len(arr)
visited = [False]*n
answer = []
def permutation(depth, result):
if depth == n:
# 리프 노드일때 결과 추가
answer.append(result)
return
for i in range(len(my_list)):
if not visited[i]:
visited[i] = True
permutation(depth+1, result+[my_list[i]])
visited[i] = False
permutation(0, [])
print(answer) # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
# 조합
# 전체 수 n을 입력받아 k개의 조합을 리턴하라
n = 4
k = 2
arr = [x for x in range(1,n+1)]
visited = [False]*n
answer = []
visited = [False]*n
def combination(depth, result, start):
if depth == k:
answer.append(result)
return
for i in range(start, len(my_list)+1):
if not visited[i]:
visited[i] = True
combination(depth+1, result+[arr[i]], i)
visited[i] = False
combination(0,[],0)
print(answer) # [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
