C++ STL next_permutation

순열이란 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수를 말합니다.

C++에서는 next_permutation과 prev_permutation을 이용하여 이것을 손쉽게 구할 수 있습니다.

---

next_permutation

1) next_permutation의 사용방법

#include <algorithm>으로 algorithm 헤더파일을 추가하여야 합니다. 

그리고 next_permutation에게 컨테이너의 시작과 끝 iterator를 인자로 전달하여 줍니다.

해당 컨테이너에 다음 순열이 존재하면 그 컨테이너의 다음 순열로 순서를 바꾸고 true를 반환합니다.

만약 다음 순열이 존재하지 않는다면 false를 반환합니다.

 

설명만으로는 이해하시기 어려울테니 예시를 들어서 설명을 드리겠습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
	vector <int> v;
	// { 1, 2, 3, 4 } 저장
	for (int i = 0; i < 4; i++)
		v.push_back(i + 1);

	do {
		for (auto it = v.begin(); it != v.end(); ++it)
			cout << *it << ' ';
		cout << endl;
	} while (next_permutation(v.begin(), v.end()));

	return 0;
}

 

이렇게 하면 output이 다음과 같이 나오게 됩니다.

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

(생략)

4 2 3 1

4 3 1 2

4 3 2 1

오름차순으로 시작되었던 순열이 내림차순으로 끝났음을 알 수 있습니다.

 

그러면 비슷하지만 반대에 해당하는 연산인 prev_permutation에 대해서 알아보겠습니다.

---

prev_permutation

1) prev_permutation의 사용방법

next_permutation과 마찬가지로 algorithm 헤더파일을 추가하여야 합니다.

그리고 prev_permutation에게 컨테이너의 시작과 끝 iterator를 인자로 전달하여 줍니다.

해당 컨테이너에 이전 순열이 존재하면 그 컨테이너의 이전 순열로 순서를 바꾸고 true를 반환합니다.

만약 다음 순열이 존재하지 않는다면 false를 반환합니다.

 

예시를 들어보겠습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
	vector <int> v;
	// { 4, 3, 2, 1 } 저장
	for (int i = 0; i < 4; i++)
		v.push_back(4 - i);

	do {
		for (auto it = v.begin(); it != v.end(); ++it)
			cout << *it << ' ';
		cout << endl;
	} while (prev_permutation(v.begin(), v.end()));

	return 0;
}

 

이렇게 하면 output이 다음과 같이 나오게 됩니다.

4 3 2 1
4 3 1 2
4 2 3 1
4 2 1 3
4 1 3 2
(생략)

1 3 2 4
1 2 4 3
1 2 3 4

내림차순으로 시작되었던 순열이 오름차순으로 끝났음을 알 수 있습니다.

---

추가

꼭 필요한 것은 아니지만 배울 것들이 몇 개 있어서 next_permutaion의 내부 알고리즘에 대해서 알아보겠습니다.

내부 알고리즘 코드를 보아도 이해하기가 어려웠는데 잘 소개가 된 블로그가 있어서 이곳을 참조하였습니다.

https://jeonggyun.tistory.com/110

next_permutation 알고리즘

단계는

1) 뒤에서부터 2개씩 숫자를 비교하여서 오름차순의 숫자 쌍을 찾습니다. ( {2,3}은 오름차순, {3,2}는 내림차순 )

2) 그 숫자 쌍에서 작은 숫자를 i로 그리고 큰 숫자를 k로 두겠습니다.

3) 이번에는 맨 뒤에서부터 j라는 인덱스로 i보다 큰 값을 갖는 위치에 j를 둡니다.

4) i와 j의 값을 바꾸어 줍니다.

5) k를 포함한 뒷부분을 순서를 뒤집어 줍니다(reverse)

 

위의 단계를 거쳐서 next_permutation을 진행시켜줍니다.

알고리즘 내에서 while문을 사용하여서 구현을 하였는데 그 부분을 잘 익혀두면 향후 코딩 문제를 푸는데에도 도움이 될 것 같습니다.

 

---

추가 2

next_permutation을 이용하여 combination을 구현한 신기한 코드를 보아서 추가하였습니다.

https://mjmjmj98.tistory.com/38

[C++ / Algorithm] 순열(next_permutation) 사용 방법과 조합(Combination) 구하기

해당 블로그를 참조하였습니다.

Q : {1, 2, 3, 4} 중 2개의 원소를 고르는 모든 경우의 수 출력하기

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    vector<int> s{ 1, 2, 3, 4 };
    vector<int> temp{ 1, 1, 0, 0 };
 
    do {
        for (int i = 0; i < s.size(); ++i) {
            if (temp[i] == 1)
                cout << s[i] << ' ';
        }
        cout << endl;
    } while (prev_permutation(temp.begin(), temp.end()));
}


출처: https://mjmjmj98.tistory.com/38 [Live passionate😎]

 

temp라는 배열에 1 1 0 0 으로 각각 중복된 2개의 수를 가지도록 넣습니다.

그리고 1 1 0 0 을 prev_permutation을 이용해

1 1 0 0 

1 0 1 0

1 0 0 1

0 1 1 0

0 1 0 1

0 0 1 1

로 만들어주고

각각 1일 때만 배열의 원소를 출력하면 combination을 구현할 수 있습니다.

 

permutation을 공부했어도 제 머리로는 위 알고리즘을 생각해내지 못 했을 것 같습니다..

 

이상으로 next, prev permutation에 대한 포스팅을 마치겠습니다.