python - 순열,조합 (itertools , math ) 함수 활용

python 을 이용 한다면 순열, 조합을 Java 와 같이 직접 구현할 필요가 없이 itertools 와 math 함수를 사용하여 permutation 과 combination 을 사용 할 수가 있다.

 

코딩테스트에서는 조합 문제로 풀 수 있는 문제가 자주 나와 두가지 경우 둘 다 익숙해 질 필요가 있다.

 

from itertools import permutations,combinations,product,combinations_with_replacement
from math import perm,comb,pow

lst = [i for i in range(1,6)]
N = 3
for i in permutations(lst,N):
    print(i, end=" ")

itertools 기본 출력 형식 

기본적으로 튜플로 데이터가 만들어짐

위에 코드 예시는 5P3 이다.

 

 

순열 (Permutaition) : 순서를 정해서 나열

서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 o , 중복 x)

 

itertools 와 math 함수의 차이를 본다면

print(f'math :  {perm(3,2)}')
print(f'itertools : {list(permutations([1,2,3],2))}')

 

출력결과

 

 

출력 결과 만 봤을때도 눈에 보인다.

 

math 함수는 3p2 의 계산값만 return을 하고

itertools 함수는 3p2의 파라미터로 받은 리스트의 순열로 만든결과를 값으로 return 을 해준다.

 

물론 리스트로 변환하여  len 함수를 사용하여 math 처럼 결과값을 만들어 낼수는 있지 않나 라고 생각을 하지만 만약 

많은 결과 값이 나오고 계산값만 필요하다면 math.perm() 을 활용하여 값만 사용하는게 좋고 순열,조합으로 만들어진

데이터들이 필요할 경우에는 itertools를 활용하여 반복문과 같이 활용 하는 것이 좋다.

 

---

중복 순열

- 서로 다른 n 개 중에 r개를 선택하는 경우의 수 (순서 o , 중복 o)

식 : n^r

 

lst = [i for i in range(1,6)]
print(f'{list(product(lst,repeat=2))}')
print(f'계산값 : {len(list(product(lst,repeat=2)))}')
print(f'math 계산값 : {pow(len(lst),2)}')

 

 

---

조합 (Combination) 

서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 x , 중복 x)

식 : nCr = nPr / r!

lst = [i for i in range(1,6)]

print(f'itertools 조합 : {list(combinations(lst,3))}') 
print(f'math 계산값 : {comb(len(lst),3)}')
# 5C3 5x4x3 / 3x2x1 = 10

 

---

중복 조합

서로 다른 n개 중에서 r개를 선택하는 경우의 수(순서X , 중복 O)

 

식 : n+r-1 C r

 

lst = [i for i in range(1,6)]

print(f'itertools 중복 조합 : {list(combinations_with_replacement(lst, 3))}')
print(f'math 계산값 : {comb(len(lst)+3-1 , 3)}')

 

---

 

python 에서 순열과 조합은 itertools 라이브러리와 math  함수로 값 또는 튜플데이터를 만들어 낼 수 있으며 직접 구현 하는 것보다 속도가 더 빠르다고 한다.