순열

---

구분

순서와 상관 O 뽑는다면 -> 순열
순서와 상관 X 뽑는다면 -> 조합

문제에서 아래와 같은 경우 순열

- 순서를 재배치하여 ..
- ~한 순서의 경우 MAX값을 

next_permutation

• 오름차순 기반으로 순열 만들기
• 정렬이 되지 않은 경우 모든 순열을 다 반환하지 않음 -> sort 필수
  ex. {2, 1, 3}
  • 2,1,3
  • 2,3,1
  • 3,1,2
  • 3,2,1

4가지 경우만 출력

• [from, to)

array

int a[] = {1, 2, 3};

do {
	for(int i : a) cout << i << " ";
    cout << '\n';
}while(next_permutation(&a[0], &a[0] + 3)); // a, a+3 도 가능

vector

vector<int> a = {1, 2, 3};

do {
	for(int i : a) cout << i << " ";
    cout << '\n';
}while(next_permutation(a.begin(), a.end()); 

공식

n개중에 r개를 뽑는 경우의 수

nPr = n! / (n-r)!

재귀함수

void makePermutation(int n, int r, int depth) {
   cout << n << " : " << r << " : " << depth << '\n';
   
   // 기저 사례 
   if (r == depth) {
      printV(v);
      return;
   }
    
   for(int i = depth; i < n; i++) {
      swap(v[i], v[depth]);
      makePermutation(n, r, depth + 1);
      swap(v[i], v[depth]);
   }

   return;
}