[코드테스트]순열과 조합 Permutation & Combination

순열 (Permutation)

 

순열 (Permutation)은 집합안에 숫자들이 있을때 순서를 고려하여 나열한 경우의 수를 순열이라한다. 

즉, 서로 다른 n개중 r 개를 선택해 순서를 정해 나열한 가짓수를 순열이라 정의한다. 

기호로는 Permuation의 앞글자를 따서 nPr로 표시한다. 

 

순열은 조합되는 순서가 고려됨으로 [1, 2, 3]의 리스트에서 2개 원소를 골라 순서를 정하는 순열을 고려해 보면

[(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]로 순열을 구성할 수 있다. 주의 할 점은 (1,2)와 (2,1)은 다른 것이다. 

 

# 순열작성예시

from itertools import permutations

 

arr = [1,2,3]

nPr = permutations(arr, 2)

print('결과 : ', list(nPr))

 

>>>

결과: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

 

 

---

조합 (Combination)

 

조합이란 한 집합내에서 원소가  n개 있을때 서로 다른 n개 중에서 r개 선택 (단 n≥r) 하여 소그룹을 만들때 만든 그룹을 

n개 원소중에서 r개 선택한 조합이라고 한다. 

 

조합은 순열과 다르게 순서를 고려하지 않는다. 따라서 [1, 2, 3]의 리스트에서 2개의 원소를 골라 조합을 만들면

[(1,2), (1,3), (2,3)]이 출력된다. 조합에서는 (1,2), (2,1)은 같은것으로 취급하여 중복을 허용치 않는다. 

# 조합작성예시

from itertools import combinations

 

arr = [1,2,3]

nCr = combinations(arr, 2)

print(list(nCr))

 

>>>

결과: [(1, 2), (1, 3), (2, 3)]

 

---

Code Test관점

 

Python으로 순열과 조합 작성시 Python의 itertools 라이브러리를 활용하면 

for loop 와 if문을 이용하여 순열과 조합 만들지 않아서 간편한 점이 있다. 

경험상 외부 itertools과 같은 외부라이브러리 활용시 구현은 되어도 시간복잡도에서 fail로 뜰때가 많아서

시간복잡도 측면에서 얼마나 걸리는지 확인 해 볼 필요는 있을 것 같다.