코딩 문제를 풀다보면 순열이나 조합을 구현해야할 때가 종종 있다.
물론 dfs를 이용해 직접 구현할 수도 있겠지만 시간이 중요한 상황엔 미리 만들어져 있는 algorithm헤더 아래에 있는 next_permutation()함수를 이용하는 것이 편리하다.
이 함수는 인자로 순열을 구할 배열이나 벡터의 시작과 끝의 주소나 반복자를 받는다.
next_permutation(vector.begin(), vector.end());
next_permutation(arr[0], arr[n]);
이 함수는 수행 후 다음 순열을 구하고 true를 반환하고
다음 순열이 없을 경우 false를 반환한다.
그래서 while문을 통해 해당 범위 내의 모든 순열을 탐색할 수 있다.
next_permutation()함수를 사용할 때는 우선 탐색할 배열을 정렬해 놓아야 모든 경우의 수를 구할 수 있다.
이 함수는 이전의 순열은 구하지 않고 다음 순열만 구하기 때문이다.
예를 들어 현재 배열의 상태가[3,2,1]이라면 더이상 순열을 구하지 않고 false를 반환할 것이다.
이전의 순열을 구하려면 prev_permutation()함수를 사용할 수 있다.
예시
결과
더 이상 만들 순열이 없을 때 false를 반환하는 성질 때문에 do-while문과 자주 같이 사용된다.
또 순열을 구하는 함수이지만 이 함수를 통해 보조 배열과 같이 사용해서 조합을 구현할 수도 있다.
조합은 기호로 nCr로 나타내는데 next_permutation()함수를 통해 조합을 구현하려면 우선 전체 길이가 n인 보조 배열이 필요하다.
그리고 그 배열은 r개의 원소를 1로 채우고 나머지는 0으로 채운다.
위에서 말한 것과 같이 이 배열도 정렬된 상태여야한다.
즉 1이 0 뒤에 있어야한다.
그런 후 이 배열에 대해 next_permutation()함수를 통해 순열을 구하고
이 순열을 돌며 배열의 값이 1인 인덱스에 해당하는 원래 구하려는 배열의 값을 출력하면 그 결과가 조합이 된다.
예시
결과
보조배열에 대한 순열이 이렇게 나오는데
보조 배열 값이 1인 인덱스의 조합을 구할 배열 값을 출력하면
조합의 값이 나오게 된다.
