[C++] next_permutation으로 STL Combination 함수 작성하기

next_permutation

<algorithm> 헤더파일에 존재한다.

iterator의 시작과 끝을 입력받는다. 만약 오름차순으로 정렬되어 있다면 내림차순이 될때까지 순서를 변경해준다. 변경이 가능하면 true를 리턴한다.

따라서 모든 순열을 보기 위해서는 먼저 오름차순으로 정렬해줘야한다.

이를 이용해서 순열을 구현할 수 있다.

$_5C_2$를 구현하고자 한다면 vector에 $0, 0, 0, 1, 1$을 넣어주고 next_permutation을 실행하면 된다.

단순한게 Combination값만 구하는 경우

다이나믹 프로그래밍으로 다음과 같이 구한다.

int combination(int n, int r) {
    if (n == r || r == 0)
        return 1;
    if (d[n][r]) return d[n][r];
    d[n][r] = combination(n - 1, r - 1) + combination(n - 1, r);
    return d[n][r];
}