알고리즘 - Next Permutation

✔ Next Permutation

• 현 순열에서 사전순으로 다음 순열 생성.
  0. 배열을 오름차순으로 정렬.
  1. 뒤쪽부터 탐색하며 교환 위치(i-1)찾기 (i : 꼭대기)
  2. 뒤쪽부터 탐색하며 교환 위치(i-1)와 교환할 큰 값 위치(j) 찾기
  3. 두 위치의 값(i-1, j) 교환
  4. 꼭대기 위치(i)부터 맨 뒤까지 오름차순 정렬
• 단점 : 전체 데이터를 기준으로만 가능하기 때문에 nPn만 가능.

✔ Next Permutation 활용 : 조합

• Next Permutation 조합
  1. 원소 크기와 같은 크기의 int 배열 P를 생성하여 r개 크기만큼 뒤에서 0이 아닌 값으로 초기화.
  2. 한 번의 Next Permutation마다 새로운 조합 생성.
     • Next Permutation마다 0이 아닌 값의 위치 변경.
     • 0이 아닌 값에 해당하는 원소 선택이라는 의미.

• Next Permutation 조합 예시 : 3C2

  P	{1, 2, 3}
  0, 1, 1	2, 3
  1, 0, 1	1, 3
  1, 1, 0	1, 2