[알고리즘] next_permutation - 순열과 조합 / C++

next_permutation은 C++ STL의 <algorithm> 헤더에서 제공하며

순열과 조합을 구할 때 유용하게 사용 가능한 함수이다.

 

순열과 조합

순열 : 서로 다른 n개의 원소에서 r개를 선택한 후, 이를 나열하는 모든 경우의 수.

 

기호로는 n​Pr 이라고 나타내며, 이 때의 P는 영어 permutation의 약자이다.

특정 원소를 ​뽑은 후 이를 '나열'하는 경우의 수이기 때문에, 뽑힌 원소의 순서까지도 고려가 된다.

예를 들어 {1, 2}와 {2, 1}은 같은 원소를 선택하였으나 순서가 다르기에, 둘은 다른 순열이 된다.

 

{1, 2, 3}으로 만들 수 있는 순열은 다음과 같다.

{1, 2, 3}

{1, 3, 2}

{2, 1, 3}

{2, 3, 1}

{3, 1, 2}

{3, 2, 1}

총 6개의 경우의 수가 존재한다.

 

 

 

조합 : 서로 다른 n개의 원소에서 r개를 선택하는 경우의 수.

 

기호로는 nCr이라고 나타내며, C는 combination의 약자이다.

특정 원소를 뽑는 것까지의 과정이기 때문에, 뽑는 원소의 순서는 고려되지 않는다.

예를 들어 {1, 2}와 {2, 1}은 순서는 다르지만 결국 같은 원소를 뽑은 것이기에, 동일한 조합이 된다.

 

[1, 2, 3, 4, 5] 총 5개의 원소 중 3개의 원소로 만들 수 있는 조합은 다음과 같다.

{1, 2, 3}

{1, 2, 4}

{1, 2, 5}

{1, 3, 4}

{1, 3, 5}

{1, 4, 5}

{2, 3, 4}

{2, 3, 5}

{2, 4, 5}

{3, 4, 5}

총 10개의 경우의 수가 존재한다.

 

 

 

next_permutation

주어진 순열을 사전 순의 다음 순열로 바꾸고 true를 리턴하는 함수

 

next_permutation 함수의 첫 번째 인자로는 순열을 구할 대상 시작점의 주소 혹은 iterator를, 두 번째 인자로는 끝나는 지점의 주소 혹은 iterator를 넘겨받는다. 또한 현재 순열이 사전 상에서의 마지막일 경우 true가 아닌 false를 리턴한다.

 

때문에 첫 번째 실행 후 조건에 따라 구문을 실행하는 do-while문과 연계하여 가능한 모든 순열을 만들 수 있다.

 

다만 주의점이 있다.

현재 주어진 순열을 기준으로 사전 순의 다음 순열으로 바꾸기 때문에, 처음으로 주어진 순열이 오름차순으로 정렬되어있지 않을 경우, 가능한 남은 경우의 수만을 보여주게 된다.

가능한 모든 순열을 얻고 싶을 경우, 오름차순으로 정렬된 초기값을 넘겨 주어야 한다.

 

 

 

next_permutation 예시 : 정렬된 초기값을 넘겨주었을 때

 

 

next_permutation 예시 : 오름차순으로 정렬되지 않은 초기값을 넘겨 주었을 때

 

 

구현 - 순열

next_permutation 함수와 do-while문만으로 쉽게 구현 가능

 

함수의 이름이 next_permutation, 즉 다음 순열이니만큼 별다른 응용 없이 do-while만으로도 쉽게 구현할 수 있다.

이번엔 유저로부터 총 원소의 개수와 각 원소의 값들을 입력받은 후, 오름차순으로 정렬 후 next_permutation 함수를 호출하여 모든 순열을 출력하였다.

 

 

구현 - 조합

순열과는 달리 순서가 필요 없게 되므로,
0과 1로 구성된 보조적인 수열을 선언하여 조합 구성.

 

앞서 설명했듯이, {1, 2}와 {2, 1}은 순열 상에서는 다르나 조합 상에서는 같기 때문에

next_permutation을 통해 곧바로 조합을 구현하기에는 무리가 있다.

때문에 중복을 피하기 위한 별도의 과정이 필요한데,

이 때 0과 1로 구성된 보조적인 수열을 이용하면 된다. 방법은 다음과 같다.

1. 0과 1로 구성된 오름차순의 보조 수열을 선언한다. 이 때 0의 개수는, nCm에서 m의 개수와 같다.
2. 해당 보조 수열로 next_permutation을 수행한다.
3. 그때마다 변화하는 순열을 순회하며, 값이 0일 경우에만 기존의 값을 더하여 출력해 준다.

 

예를 들어 [1, 3, 4, 7, 8]로 구성된 수열에서 3개의 원소를 선택하는 조합의 경우, 이를 위한 보조 수열은 [0, 0, 0, 1, 1]이 될 것이다.

중복된 수가 존재하는 보조 수열로 next_permutation을 수행할 경우 가능한 경우의 수는 5!가 아닌 (5! / (3! * 2!))가 될 것이고, 각각의 순열을 순회하며 0값을 가질 경우, 해당 인덱스에 해당하는 원본 수열의 값을 더해 준 후 출력하면 된다.

 

{0, 0, 0, 1, 1} => {1, 3, 4}
{0, 0, 1, 0, 1} => {1, 3, 7}
{0, 0, 1, 1, 0} => {1, 3, 8}
{0, 1, 0, 0, 1} => {1, 4, 7}
{0, 1, 0, 1, 0} => {1, 4, 8}
{0, 1, 1, 0, 0} => {1, 7, 8}
{1, 0, 0, 0, 1} => {3, 4, 7}
{1, 0, 0, 1, 0} => {3, 4, 8}
{1, 0, 1, 0, 0} => {3, 7, 8}
{1, 1, 0, 0, 0} => {4, 7, 8}

---

유저로부터 총 원소의 개수와 원소의 값들

그리고 그 중에서 선택할 원소의 총 개수를 입력받아 조합을 수행하도록 구현해 보았다.

 

 

기본적으로 모든 경우의 수를 구현하는 문제에서는 백트래킹 등을 이용할 수 있겠지만, 순열과 조합이 필요한 상황에서는 next_permutation 함수를 적절하게 사용하여 보다 쉽게 문제를 해결할 수 있을 것이다.