순열과 조합 그리고 중복순열과 중복조합 (파이썬에서 사용 방법)

순열과 조합

순열과 조합은 경우의 수를 구할 때 사용하는 것이다.

세상은 수많은 경우의 수가 존재한다. 우리가 무엇을 선택해야할 때 이 경우의 수를 따진다.

예를 들어서 재료가 5가지가 있고 요리에 3가지 재료를 넣을 수 있을 때 (재료를 넣을 때 순서가 중요한 경우있을 때 순서가 있다고 볼 수 있음. 이 경우 순열)

, 냉장고에는 5가지 반찬이 있고 식탁에 올릴 3가지 반찬을 올려야 할 때. (식탁에 올리는 순서나 위치가 중요하지 않을 때는 조합이라고 볼 수 있음. 이 경우 조합)이다.

 

위 정의를 잘 이해한다면 경우의 수를 구하는 공식만을 구하면 된다.

팩토리얼

! (팩토리얼 기호)

n 팩토리얼일 경우 1이 될 때까지 1씩 감소시킨 값들을 모두 곱하는 것이다.

순열

순열은 경우의 수에 순서나 위치라는 개념이 존재(1등, 2등, 3등 처럼)할 때의 경우의 수를 말한다.

우선 n은 우리에게 주어진 모든 수의 양을 의미하고 r은 그 중에 선택할 수 있는 수의 양을 의미한다.

즉 5명에서 2명을 일렬로 세울 때, 5명은 n을 의미하고 2명은 r을 의미한다.

nPr의 경우 n을 1씩 감소시켜 r보다 1큰 값들을 모두 곱한 값이다.

6명 중에서 2명을 뽑아 세울 때 (위치가 중요한 경우일때, 순열) 6팩토리얼 나누기 4팩토리얼이 된다.

그러므로 6*5가 정답.

조합

조합은 순열과 달리 순서나 위치라는 개념이 없다. 예를 들어 우리가 반 전체에서 2명을 뽑아 우수상을 줄 때, 철수와 영희가 받는다면 (철수, 영희) (영희, 철수) 이 두가지의 경우는 하나의 경우이다. 그렇기 때문에 하나를 제거해주어야 한다.

공식은 위와 같다. 예를 들어 6명 중 3명의 대표자를 뽑을 때 아래와 같이 표현되어 있다.

중복순열, 중복조합

중복 순열과 중복 조합은 사실 별것이 없다. 예를 들어 10명의 인원으로 제비뽑기를 할 때 2번을 뽑는다. (순서 상관이 없을 것이다.) 이 때 뽑은 종이를 버리지 않고 다시 넣는다면(복원 추출) 해당 종이가 2번 나올 수 있는 경우의 수가 있다.

보통 순열과 조합은 위와 같은 경우를 고려하지 않는다.(비복원 추출) 중복순열과 중복조합은 중복이 가능할 때를 의미한다. 

중복순열은 n의 r제곱을 해준다.

중복조합은 

위와 같다.

파이썬에서 사용하려면

파이썬에서 itertools 라이브러리를 사용하면 된다.

순열은 permutations 함수이고 이 함수에 iterable한 변수와 뽑아야 하는 것의 수를 넣어주면 된다.

from itertools import permutations

arr = [0,1,2,3,4]
M = 2

list(permutations(arr, M))

조합은 combinations 함수이고, 이 함수에 사용법은 permutations와 같습니다.

중복 순열은 product 함수, 중복 조합은 combinations_with_replacement 함수입니다.