[순열]01. 순열의 개요

순열의 정의

순열(Permutation)이란 n개의 원소에서 r개를 중복을 허용하지 않고 선택해서 순서대로 늘어놓은 것을 말하며 nPr이라고 표기한다.

순열의 전개 과정

4개의 원소 {1,2,3,4}에서 3개를 선택해서 순서대로 나열하는 방법에 대해 생각해보자.

맨 처음은 4개의 원소가 모두 올 수 있다. 

 

그 다음은 각 경우에 대해 중복을 허용하지 않으므로 1st에서 선택되지 않은 3녀석이 각각 올 수 있다. 즉 4*3 가지가 가능하다. 여기서 1-4와 4-1은 당연히 다르다. 우리는 순서대로 나열하고 있다는 점이 중요하다.(만약 순서가 상관 없이 뽑기만 진행한다면 조합이 된다.)

 

동일한 절차를 거치면 우리가 원하는 순열을 얻을 수 있다.

드디어 모든 절차가 끝났고 4개의 원소에서 중복 없이 3개를 선택하는 방법은 총 4*3*2 = 24가지이다.

이 과정이 수학적으로는 어떻게 동작했을까?

 

4개의 요소에서 3개를 뽑아서 나열하는 과정은 4P3이다. 

4P3은 위에서 살펴봤듯이  4*3P2이고 이는 다시 4*3*2P1이 된다. 이처럼 순열은 처음에는 4P3이어서 매우 큰 문제인줄 알았는데 2P1로 줄었고 이 과정이 끝나면 드디어 원하는 결과를 얻게 된다. 

즉 재귀를 통해서 큰 문제를 작은 문제로 처리하면 원하는 결과를 얻을 수 있다.

 

이제 다음 포스트에서 순열을 구현해보자.