[C++] 순열

1. 순열

 

서로 다른 n개의 원소에서 r개를 중복 없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다.

 

---

2. next_permutation

 

[Algorithm] C++에서 next_permutation 함수(혹은 prev_permutation 함수)를 통해서 순열 구하기

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

• next_permutation: 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.
• prev_permutation: 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 크다면) false를 반환.

 

이때 중요한 것은 주어진 벡터 혹은 배열을 [from, to) 범위에서 다음 순열로 변경한다.

 

커스텀비교함수를 사용할 수 있다.

 

#include<bits.stdc++.h>
//#include<iostream>
//#include<algorithm>
using namespace std;
int main(){
    int a[] = {1,2,3}; //오름차순으로 정리된 배열이 필요함.
    do{
        for(int i : a) cout << i << " ";
        cout << '\n';
    }while(next_perutation(&a[0], &a[0] + 3));
}

 

 

---

3. 재귀함수를 사용한 순열

 

#include<iostream>
#include<vector>
using namespace std;
vector<int> v;

void printV(vector<int> v){
	for(int i : v) cout << i << " ";
	cout << '\\n';
}

// n개 중에 r개를 뽑는다.
void makePermutation(int n, int r, int depth){
	if(r == depth){
		printV(v);
		return;
	}
	for(int i=depth; i < n; i++){
		swap(v[i], v[depth]);
		makePermutation(n, r, depth + 1);
		swap(v[i], v[depth]);
	}
}

int main(){
	for(int i=1; i<4; i++){
		v.push_back(i);
	}
	makePermutation(3,2,0);
	return 0;
}

/*
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
*/

 

 

---

 

[알고리즘] 2309번: 일곱 난쟁이 (수정)