0. 서두
- 알고리즘 문제 풀이에 필요한 순열과 조합을 정리한다.
1. 순열
- Permutation
- 서로 다른 n개 중 r개를 골라 순서를 정해 나열하는 가짓수이다.
- 다시 말하면 n개 중에 r개를 선택하여 만들 수 있는 모든 경우의 수를 의미한다.
def perm(arr, n):
result = []
if n > len(arr):
return result
if n == 1:
for i in arr:
result.append([i])
elif n > 1:
for i in range(len(arr)):
ans = [i for i in arr]
ans.remove(arr[i])
for j in perm(ans, n-1):
result.append([arr[i]]+j)
return result
arr = [1, 2, 3]
print(Perm(arr, 1))
print(Perm(arr, 2))
print(Perm(arr, 3))
2. 조합
- Combination
- 서로 다른 n개 중에서 r개를(n≥r) 취하여 조를 만들 때, 각각의 조를 조합이라고 한다
- 다시 말하면 n개 중에 r개를 순서에 상관 없이 뽑은 경우의 수를 의미한다.
def comb(arr, n):
result = []
if n > len(arr):
return result
if n == 1:
for i in arr:
result.append([i])
elif n > 1:
for i in range(len(arr)-n+1):
for j in comb(arr[i+1:], n-1):
result.append([arr[i]]+j)
return result
arr = [1, 2, 3]
print(comb(arr, 1))
print(comb(arr, 2))
print(comb(arr, 3))
- 내장함수로 쉽게 순열과 조합을 사용할 수 있다.
- 다만 itertools는 코딩 테스트에서 사용하지 못하는 경우가 있으므로 직접 구현하는 방법을 먼저 익히는 것이 중요하다.
from itertools import combinations
from itertools import permutations
arr = [1, 2, 3]
print(list(combinations(arr, 2)))
print(list(combinations(arr, 3)))
print(list(permutations(arr, 2)))
print(list(permutations(arr, 3)))