[C++] 순열을 만드는 함수 : next_permutation()

순열과 조합은 이미 중고등학교 때 배운 개념일텐데, 코딩테스트를 준비할 때에도 중요한 개념이다.

순서에 상관 있게 뽑는 것을 순열

순서에 상관 없이 뽑는 것을 조합 이라고 한다.

예를 들어, {1,2,3} 에서 3개를 순열로 뽑으면 3P3으로 {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} 여섯 가지(3!),

                                     3개를 조합으로 뽑으면 3C3으로 {1,2,3} 한 가지이다.

 

순열 1. STL next_permutation

c++에서는 next_permutation() 함수를 제공하는데, 이는 오름차순을 기준으로 정렬된 배열을 순열로 만든다.

반드시 오름차순 정렬되어 있어야 한다.

 

next_permutation()의 매개변수(parameters)는 순열을 시작할 범위의 첫 번째 주소, 마지막 주소이다.

단, 주의 할 것은 [first,last) 범위이다. 

do while문을 사용해 벡터의 순열을 출력하는 예시 코드를 보자.

#include <bits/stdc++.h>
using namespace std;
vector<int> v = {1,3,2};

int main() {				
	sort(v.begin(), v.end());				// 1. 오름차순 정렬
    
	do {							// 2. 순열 출력
		for (int i:v) cout << i << ' ';
		cout << '\n';	
	}
	while(next_permutation(v.begin(), v.end()));
}

[출력]
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

위와 같이 오름차순 정렬인 sort()와 함께 쓰는 것이 좋다.

 

아래는 c++ reference이다.

https://en.cppreference.com/w/cpp/algorithm/next_permutation

std::next_permutation - cppreference.com

 

순열 2. 재귀를 이용한 방법

int a[10];
int n=5, r=3;
bool used[10];
void per(int depth){
	if (depth == r){
		for(int i=0; i<r; i++) cout << a[i] << ' ';
		cout << '\n';
	}
	for(int i=1; i<=n; i++){
		if (!used[i]){
			a[depth] = i;
			used[i] = 1;
			per(depth+1);
			used[i] = 0;
		}
	}
	return;
}

int main(){
	per(0);
}

 

조합 1. 중첩 for문을 사용한 방법

 #include <bits/stdc++.h>
 using namespace std;
 int n = 5, k = 3;
 int a[5] = {1, 2, 3, 4, 5};
 
 int main() {
 	for(int i = 0; i < n; i++){
 		for(int j = i + 1; j < n; j++){
 			for(int k = j + 1; k < n; k++){
 				cout << i << " " << j << " " << k << '\n';
 			}
		 }
 	}
 	return 0;
 }

조합 2. 재귀를 이용한 방법

#include <bits/stdc++.h>
using namespace std;
int a[5] = {1,2,3,4,5};
vector<int> b;
int n=5, k=3;

void combi(int start, vector<int> b){
	if (b.size() == k){
		for(int i:b) cout << i << ' ';
		cout << '\n';
		return;
	}
	for(int i=start+1; i<n; i++){
		b.push_back(i);
		combi(i, b);
		b.pop_back();
	}
	return;
}

int main(){
	combi(-1,b);
	return 0;
}