[알고리즘] 순열, 조합 응용: Next Permutation

0. Next Permutation

현 순열에서 사전 순으로 다음 순열을 생성하는 것

 

이를 이용하여 순열과 조합을 표현할 수 있다.

재귀를 통해 구현한 순열, 조합보다 빠르다는 장점을 가지고 있다.

하지만 nPn만 가능하다는 단점을 가지고 있다.

---

1. 알고리즘

• 배열을 오름차순으로 정렬한다.
• 아래 과정을 반복하여 사전 순으로 다음을 큰 순열을 생성한다.(가장 큰 순열을 만들 때까지 반복)
  1. 뒤에서부터 탐색하며 교환 위치(pivot) 찾기 → 최초로 pivot < pivot+1이 되는 위치
  2. 뒤에서부터 탐색하며 교환 위치(pivot)와 교환할 위치(successor) 찾기 → pivot < successor 중 가장 작은 값의 위치
  3. 두 위치(pivot, successor) 값 교환
  4. 교환 위치(pivot)의 뒷 부분을 오름차순으로 정렬
• NextPermutation 사용 전에 숫자배열을 오름차순으로 정렬한 시작 시점의 순열을 한 번 처리해야 한다.

---

2. 순열 코드

---

3. 조합 코드

nCr일 때, n개의 배열에 r개에는 1을 (n - r)개에는 0을 저장한다.

생성한 배열에 Next permutation과 동일한 알고리즘을 적용한다.

각 배열 값에서 1이면 선택, 0이면 미선택으로 생각하면 조합이 된다.