C++ STL 의 <algorithm> 헤더에서 제공하는 next_permutation, prev_permutation 함수에 대해 알아보려고 한다.

순열과 조합

순열

Permutation : 서로 다른 n 개의 원소에서 r (0 < r ≤ n) 개를 중복없이 순서를 고려하여 선택하거나 나열하는 것

(n 명의 사람 중 r 명을 골라 줄 세우는 경우의 수 = n)

조합

Combination : 서로 다른 n 개의 원소에서 r (0 < r ≤ n) 개를 중복없이, 순서를 고려하지 않고 선택하는 것

(n 명의 사람 중 r 명을 선택하는 경우의 수)

next_permutation

주어진 순열을 사전 순의 다음 순열로 바꾸는 함수

next_permutation(BidirectionalIterator first, BidirectionalIterator last);

• do-while 문을 활용하여 가능한 모든 순열을 만들 수 있음.
• 가능한 모든 순열을 만들고 싶은 경우, 오름차순으로 정렬된 초기값을 넘겨주어야 함.

prev_permutation

주어진 순열을 사전 순의 이전 순열로 바꾸는 함수.

prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

• do-while 문을 활용하여 가능한 모든 순열을 만들 수 있음.
• 가능한 모든 순열을 만들고 싶은 경우, 내림차순으로 정렬된 초기값을 넘겨주어야 함.

매개 변수

BidirectionalIterator 란?
C++ 에서 제공하는 반복자(Iterator) 의 한 종류로, 양방향으로 움직일 수 있는 반복자.

first : 순열을 구할 시작 Iterator, 또는 배열의 시작 주소
last : 순열을 구할 끝 Iterator, 또는 배열의 끝 주소

리턴 값

현재 탐색하고 있는 순열의 다음(또는 이전) 순열을 구하고 true 를 반환.

만약 다음(또는 이전) 순열이 존재하지 않는다면, false 를 반환

즉, 마지막 모든 순열의 경우의 수를 탐색한 뒤, false 를 반환

예시

{1,2,3,4} 중 4개의 원소를 중복 없이 순서를 고려하여 나열
1234 , 1243 , 1324 , 1342 , 1423 , 1432,
2134 , 2143 , 2314 , 2341 , 2413 , 2431,
3124 , 3142 , 3214 , 3241 , 3412 , 3421,
4123 , 4132 , 4213 , 4231 , 4312 , 4321,
의 경우로 총 24개.

구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int array[4] = { 1,2,3,4 };
	do
	{
		for (int i = 0; i < 4; ++i)
			cout << array[i] << ' ';
		cout << '\n';
	} while (next_permutation(array, array + 4));
    
    return 0;
}

{1,2,3,4} 중 2개의 원소를 중복 없이 순서를 고려하여 나열
12 , 13 , 14 ,
21 , 23 , 24 ,
31 , 32 , 34 ,
41 , 42 , 43
의 경우로 총 12개.

구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<int> v = { 1,2,3,4 };
	int n = v.size();
	int r = 2;
	
	do
	{
		for (int i = 0; i < r; ++i)
			cout << v[i] << ' ';
		cout << '\n';

		reverse(v.begin() + r, v.end());
	} while (next_permutation(v.begin(),v.end()));

	return 0;
}

reverse(v.begin() + r , v.end()) 를 해주는 이유 ?

1 2 (3 4 5) 의 다음 순열로 1 2 (3 5 4) 가 아닌 1 3 (2 4 5) 를 뽑아야 한다.

reverse 함수를 통해 r(= 2) 번째부터 마지막 원소까지 3 4 5 를 뒤집어 5 4 3 로 만든다.

그러므로, 1 2 (3 4 5) 를 출력한 뒤, reverse 를 진행한 뒤의 벡터는 1 2 (5 4 3) 이 되고, next_permutation 를 통해 1 3 (2 4 5) 를 출력하게 된다.

조합

순열과 달리 순서가 필요 없으므로, 0 과 1 로 구성된 수열을 선언하여 조합을 구성

n 개의 원소에서 r 개를 중복없이, 순서를 고려하지 않고 뽑기 위해
r 개의 0 과 n - r 개의 1 로 이루어진 수열 tmp 를 생성한다.

이후, tmp 수열을 next_permutation 함수를 통해 탐색하는 경우,
n ! 이 아닌 n! / ( r! * (n-r)! ) 이 된다. ( 0 과 1 이 중복되기 때문에)

tmp 수열을 탐색하며 원소가 1일 때, 해당 인덱스에 해당하는 원본 수열을 출력하면 된다.

{1,2,3,4} 중 2개의 원소를 중복 없이 순서를 고려하지 않고 선택
12 , 13 , 14,
23 , 24 ,
34
의 경우로 총 6개.

구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<int> v = { 1,2,3,4 };
	int n = v.size();
	int r = 2;

	vector<int> tmp = { 0,0,1,1 };

	do
	{
		for (int i = 0; i < n; ++i)
		{
			if (tmp[i] == 0)
				cout << v[i] << ' ';
		}
		cout << '\n';

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

	return 0;
}

순열이나 조합이 필요한 경우, <algorithm> STL 의 next_permutation 과 prev_permutation 함수를 활용하자.