[C++] 순열&조합 구하는 함수 next_permutation

[C++] next/prev_permutation

* 개인적인 공부 내용을 기록하는 용도로 작성한 글 이기에 잘못된 내용을 포함하고 있을 수 있습니다.

 

_contents

#1 순열이란?

#2 next_permutation

#3 주의점

#4 조합 구현하기

 

_Fix

→ 2022-09-11 #4 조합 구현하기 추가

---

#1 순열과 조합

순열[permutation]이란 순서가 부여된 서로 다른 n개의 원소에서 r개의 원소를 뽑아 한 줄로 세우는 모든 경우의 수를 의미한다. 

예를 들어 {1, 2, 3} 집합의 원소들의 모든 순열을 구하면 다음과 같다.

{1, 2, 3} {1, 3, 2} {2, 1, 3} {2, 3, 1} {3, 1, 2} {3, 2, 1}

이러한 순열을 기호로 나타내는 경우 영어 Permutation의 첫 글자 P를 이용해 nPr 이라고 한다.

nPr이란 서로 다른 n개의 원소 중에서 r개를 뽑아 줄을 세운다는 뜻이다. 

 

조합[Combination]이란 순서가 부여되지 않은 n개의 원소에서 r개의 원소를 뽑아 한 줄로 세우는 모든 경우의 수를 의미한다.

앞에서 순열은 {1, 2, 3}과 {1, 3, 2}를 다른 케이스로 계산했지만, 조합은 같은 케이스로 다룬다. 따라서 

{1, 2, 3} 집합의 원소들 중에서 2개의 원소를 뽑는 조합을 구하면 다음과 같다.

{1, 2} {1, 3} {2, 3}

조합을 기호로 나타낼 때 영어 Combination의 첫 글자 C를 이용해 nCr과 같이 나타낸다.

nCr이란 순서가 부여되지 않은 n개의 원소 중 r개의 원소를 뽑아 줄을 세운다는 의미이다. 

 

순열과 조합을 직접 구현할 수 도 있지만 코딩테스트에서 순열/조합 알고리즘을 하나하나 구현 하고 있는 것은 비효율적이다.

C++ STL <algorithm> 헤더의 next_permutation 함수를 사용하면 순열과 조합의 경우의 수를 손쉽게 구할 수 있다.

---

#2 next_permutation

#include <algorithm>

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

* STL <algorithm> 헤더에서 C++11 버전 이후부터 제공한다.

 

Parameters

 

next_permutation 함수는 순열을 구할 ①시작과 끝의 iterator 혹은 배열의 경우 ②시작과 끝의 주소를 입력받는다.

 

Return Value

현재 탐색하고 있는 순열의 다음 순열을 구하고 true를 반환한다.

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

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

 

Example

다음은 {1, 2, 3} 집합을 next_permutation 함수를 사용해 집합의 모든 조합을 구한 예제이다.

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

int main(){
	//INPUT
	// vector v 1 ~ 3 까지의 원소를 대입
	vector<int> v(3);
	for(int i = 0; i < 3; ++i)
		v[i] = i + 1;
	
	// next_permutation
	do{
		for(int i = 0; i < 3; ++i)
			cout << v[i] << " ";
		cout << '\n';
	}while(next_permutation(v.begin(), v.end()));
	
	return 0;
}

[출력결과]
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

---

#3 주의점

next_permutation 함수를 사용할 때 주의 해야할 사항이 있다.

모든 순열의 경우의 수를 탐색하기 위해서는 반드시 사전에 배열 혹은 벡터를 미리 정렬해 두어야 한다.

next_permutation 함수는 이전 크기의 순열의 조합은 탐색하지 않는다. 예를들어 벡터 안의 원소가 {2, 3, 1} 로 정렬 되어 있다고 가정해 보자.

{2, 3, 1} 벡터를 next_permutaiton 함수를 사용해 모든 순열을 출력해 보면 {2, 3, 1} {3, 1, 2} {3, 2, 1} 만을 탐색하고 앞부분 {1, 2, 3} {1, 3, 2} {2, 1, 3} 은 탐색하지 않는다.

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

int main(){
	//INPUT
	vector<int> v(3);
	v[0] = 2;
	v[1] = 3;
	v[2] = 1;
	
	// next_permutation
	do{
		for(int i = 0; i < 3; ++i)
			cout << v[i] << " ";
		cout << '\n';
	}while(next_permutation(v.begin(), v.end()));
	
	return 0;
}

[출력결과]
2 3 1
3 1 2
3 2 1

 

따라서 모든 순열의 경우의 수를 구하고 싶다면 다음과 같이 sort 함수를 이용해 미리 오름차 정렬한 뒤 next_permutation 함수를 적용 하는 것을 권장한다.

#include <iostream>
#include <vector>
#include <algorithm> // next_permutation & sort
using namespace std;

int main(){
	//INPUT
	vector<int> v = {2, 3, 1};
	
	sort(v.begin(), v.end());
	// next_permutation
	do{
		for(int i = 0; i < 3; ++i)
			cout << v[i] << " ";
		cout << '\n';
	}while(next_permutation(v.begin(), v.end()));
	
	return 0;
}

[출력결과]
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

---

#4 조합 구현하기

next_permutation 함수와 보조수열을 이용해 조합을 구현할 수 있다. 

 

next_permutation 함수를 이용해 nCr을 구하는 알고리즘은 다음과 같다.

1. 전체 길이가 n , 1의 개수가 r , 나머지가 0으로 채워진 보조 수열을 생성한다. (단, 1은 뒤에서 부터 채워져 있어야 한다.)

2. 보조수열에 대한 조합을 모든 순열을 구한다. 

3. 보조수열을 순회하며 index가 1인 위치와 일치하는 원래 수열의 인덱스의 값을 출력한다. 

 

예를들어 {1, 2, 3, 4} 배열의 원소들 중에서 2개의 원소를 택하여 조합을 구하고 싶다면 즉, 4C2를 구현하고자 한다면 보조 수열을 다음과 같이 작성하면 된다.

	vector<int> v {1, 2, 3, 4};
	// visited - 보조수열
	vector<int> visit {0, 0, 1, 1};

이 때 보조수열의 1은 뒤에서 부터 채워져 있어야 하는데, 이는 앞에서 설명한 바와 마찬가지로 next_permutation 함수는 오름차로 정렬되어 있지 않으면  앞 순서의 순열을 무시한다는 특성 때문이다. 

 

다음으로 보조수열을 next_permutation 함수를 이용해 순회하며 인덱스가 1인 경우에만 원래 수열의 원소를 출력해 주면 된다.

	do{
		for(int i = 0; i < v.size(); ++i)
			if(visit[i] != 0)
				cout << v[i] << " ";
		cout << '\n';
	}while(next_permutation(visit.begin(), visit.end()));

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

 

원리는 간단하다.

보조수열의 순열을 쭉 나열해보면 다음과 같다. 

	vector<int> visit {0, 0, 1, 1};
	do{
		for(int i = 0; i < visit.size(); ++i)
			cout << visit[i] << " ";
		cout << '\n';
	}while(next_permutation(visit.begin(), visit.end()));

 

next_permutaiton 함수는 "중복을 제외한" 조합을 구하는 함수이기에

"중복을 제외한" 보조순열에 대한 모든 케이스, 총 6가지가 출력된다.

0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0

 

이제 여기서 보조수열의 인덱스가 1인 위치와 원래 구하고자 하는 배열의 원소와 비교해보면?

 

1 2 3 4
---------
0 0 1 1 ... 3 4
0 1 0 1 ... 2 4
0 1 1 0 ... 2 3
1 0 0 1 ... 1 4
1 0 1 0 ... 1 3
1 1 0 0 ... 1 2

 

4C2 총 6가지의 순열이 출력되게 되는 것이다.

---