- 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열이라고 한다.
- 이를 기호로 아래와 같이 나타낸다
예시
- 10명 중 3명을 뽑아 일렬로 세우는 경우의 수는?
- 순열의 시작은 오름차순이고 순열의 끝은 내림차순이다.
- 순열의 시작:
0, 1, 2, 3, 4, 5, 6 - 순열의 끝:
6, 5, 4, 3, 2, 1, 0
- 순열의 시작:
6, 2, 1, 5, 4, 3, 0이라는 순열이 있을 때 다음 순열을 구해보자.- 먼저 시퀀스에 뒤쪽에서 부터 내림차순 시퀀스를 구한다.
6, 2, 1, [5, 4, 3, 0][5, 4, 3, 0]이 내림차순 시퀀스다.- 내림차순 시퀀스의 바로 전 번호인
1을 기준으로 마지막 순열이라는 의미다. - 즉
1을 기준으로 더이상 다음 순열이 없기 때문에1다음의 원소 교체해 순열 탐색을 이어가야한다.
- 이제 내림차순 시퀀스의 바로 전 번호
1과 내림차순 시퀀스에 포함된 바로 다음 번호와 스왑한다. - 스왑 결과 :
6, 2, 3, [5, 4, 1, 0]1의 바로 다음인3과 스왑한다.
- 이제 3을 기준으로 처음 순열부터 탐색해야하니 3을 기준으로 오른쪽을 오름차순 정렬한다.
6, 2, 3, [0, 1, 4, 5]6, 2, 1, 5, 4, 3, 0의 다음 순열은6, 2, 3, 0, 1, 4, 5이다.
함수 구현
- 다음을 만족하는 가장 큰 인덱스
i찾기
array[i - 1] < array[i]- 만약 i가 존재하지 않으면 마지막 순열이다.
- 다음을 만족하는 가장 큰 인덱스
j찾기array[i - 1] < array[j]i <= j
- array[i - 1] 과 array[j] 를 스왑
- array[i] 부터 배열 끝까지 순서 뒤집기
연습문제
- 서로 다른 n개의 원소를 가지는 어떤 집합에서 순서에 상관없이 r개의 원소를 선택하는 것을 조합이라고 한다.
- 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 찾는 것과 같다.
- n개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수를
이항계수라 하며 아래와 같은 기호로 표시한다. $$ nCk = C(n, k) = {n \choose k} = {P(n,k) \over k!} = {n! \over k! \times (n - k)!} $$
예시
- 10명 중 3명을 뽑는 경우의 수는?
참고