nPr 구할때는 reverse 사용.

• reverse 사용하지 않으면 중복값이 나온다.
  

• reverse 사용하면 중복처리된다.
  

=> 이에 대해 알아보자..

next_per 의 원리

https://maconam.tistory.com/12

• 현재 컨테이너를 기준으로 사전순으로 그 다음으로 큰 순열을 재배치하고, true를 반환함.

• 더 이상 작은 순열이 없으면 false를 반환한다고 한다...

예를 들어 1,2,3으로 진행하는데, 3,2,1 과 같은 내림차순 단 하개 구성되면 종료된다.

코드를 보면,

• 즉 , 속하지 않은 begin() + r, ~ end까지를 오름차순이 아닌 상태로 만들고 있는 것이다.

원리

• nPr 이라고 한다면 n개 중에서 r개를 뽑는 것인데,

• 1)첫번째 원소부터 진행하는 것이므로, 일단 sort 하자.

• 2) 이 상태에서 begin() + r 이전까지 뽑는 것이고, 이제 뒤의 원소에서의 순열을 못하게 하기 위해서 reverse 를 통해서 내림차순으로 만들자는 것이다.

• 예를 들어 1,2,3,4 에서 2개 뽑으면 맨 처음에는 1,2가 나와야 한다. 그런데 뒤의 3,4에 대해서 순열 진행하지 않게 하기 위해서 // 예를 들어 1,2,4,3

-> 1,2,4,3 형태로 만들면 next_permutation 입장에서 내림차순이므로, 1,2,3,4 다음인 1,2,4,3을 구하지 않는다는 것이다.

• 이 상태에서 1,2 vs 4,3 을 가지고 순열을 진행한다고 한다.
• 이제 1,3을 구하기 위해서 1,2,3,4 형태에서 새로운 순열 만들지 않기 위함이다.

코드

• 직접 확인하기..

#include <string>
#include <vector>
#include <iostream>

using namespace std;
#include <cmath>
#include <algorithm>

vector<vector<int>> answer; 


int main(void)
{
    ios::sync_with_stdio(false),
        cin.tie(NULL), cout.tie(NULL);

	int n = 4; // 총 원소 개수
	int r = 2; // 뽑을 원소 개수
	vector<int> v = { 1, 2, 3, 4 }; // {1, 2, ..., n}

	// 1. 순열 시작을 위해 정렬 (필수)
	sort(v.begin(), v.end());

	// 2. next_permutation으로 순열 출력
	do {

		// 3. 뒷부분(r부터 n까지)을 뒤집어 줌으로써 
		// 1 2 3 4 -> 1 2 4 3 으로 넘어가는 것 방지 (r개만 선택)

		cout << "순열 진행 : 뒤집기 전 " << endl;
		for (int i = 0; i < n; ++i) {
			cout << v[i] << " ";
		}
		cout << '\n';

		cout << "r개만 뽑자. " << endl;
		for (int i = 0; i < r; ++i) {
			cout << v[i] << " ";
		}
		cout << '\n';

		

		cout << "뒤집은 후  " << endl;

		// 뒤 집으면? 
		reverse(v.begin() + r, v.end());
		for (int i = 0; i < n; ++i) {
			cout << v[i] << " ";
		}
		cout << '\n';

	} while (next_permutation(v.begin(), v.end()));


}