코딩테스트 - 순열과 조합

순열과 조합은 확률과 통계에서 경우의 수를 공부할 때 배운 것 같다. 내가 이거를 코테를 준비하면서 다시 배울줄이야..사실 순열과 조합을 배우지 않아도 문제를 푸는데 지장은 없을 것 같은데 있으면 편한 거는 사실이니까 정리하려 한다.

1. 순열 = Permutations
   리스트 같은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 경우를 순열이라 한다. 즉, 조합의 중복이 있어도 상관 없는 경우에 사용한다. 전체 데이터 중에서 일부를 선택하면 다양한 조합이 나온다. 그 조합들 중에서 중복이 있어도 되는 경우 혹은 순서가 중요한 경우에 사용한다. 파이썬에서는 from itertools import permutations로 호출해서 사용한다.

from itertools import permutations
data = list(range(4))

result = list(permutations(data, 3))
print('순열 결과: ', result)

출력

순열 결과: [(0, 1, 2), (0, 1, 3), (0, 2, 1), (0, 2, 3), (0, 3, 1), (0, 3, 2), 
           (1, 0, 2), (1, 0, 3), (1, 2, 0), (1, 2, 3), (1, 3, 0), (1, 3, 2), 
           (2, 0, 1), (2, 0, 3), (2, 1, 0), (2, 1, 3), (2, 3, 0), (2, 3, 1), 
           (3, 0, 1), (3, 0, 2), (3, 1, 0), (3, 1, 2), (3, 2, 0), (3, 2, 1)]

2. 조합 = Combinations
   순열과는 다르게 r개의 데이터를 뽑아 순서없이 일렬로 나열하는 경우를 조합이라 한다. 조합의 중복이 없어야하는 경우에 사용한다. 예를 들어 전체 데이터 중에서 일부를 선택해야 하면 다양한 조합이 나온다. 그 조합들 중에서 중복이 있으면 안되는 경우에 사용한다. 순열과 마찬가지로 파이썬에서는 from itertools import combinations로 호출해서 사용한다.

from itertools import combinations
data = list(range(4))

result = list(combinations(data, 3))
print('조합 결과: ', result)

출력

조합 결과: [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]

3. 중복 허용
   위에 예시들은 전부 중복을 허용하지 않은 것들이다. 하지만 문제를 풀다보면 중복을 허용할 때도 있다. 중복을 허용하는 경우에는 다른 라이브러리를 호출해서 사용한다.

• 중복 순열
  중복을 허용한 순열이다. from itertools import product로 호출해서 사용한다. product() 안에 repeat은 뽑는 갯수이다. 중복을 허용하는 횟수는 선언할 수 없는 것 같다. 예를 들어 5개의 데이터에서 3개를 뽑는데 중복을 2번만 허용하는 경우도 있을 수 있는데 따로 선언할 수는 없는 것 같다.

from itertools import product
data = list(range(4))

result = list(product(data, repeat=2))
print('중복순열 결과:', result)

출력

중복순열 결과: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), 
              (2, 0), (2, 1), (2, 2), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3)]

• 중복 조합
  중복을 허용한 조합이다. from itertools import combinations_with_replacement로 호출해서 사용한다. 라이브러리가 길어 as로 별칭을 정해서 사용해도 된다. 안에 r은 repeat과 같은 역할이다.

from itertools import combinations_with_replacement
data = list(range(4))

result = list(combinations_with_replacement(data, r=2))
print('중복조합 결과:', result)

출력

중복조합 결과: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), 
              (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]