Permutation

완전 탐색(브루트 포스)에서 자주 사용
#include <iostream>
#include <vector>
void swap(int& a, int& b){
char tmp=a;
a=b; b=tmp;
}
void permutation(std::vector<int> data, std::vector<std::vector<int>>& ret, int depth, int n, int r){
if(depth==r){
std::vector<int> tmp_data(r);
copy(data.begin(), data.begin()+r, tmp_data.begin());
ret.push_back(tmp_data);
return;
}
for(int i=depth; i<n; ++i){
swap(data[depth], data[i]);
permutation(data, ret, depth+1, n, r);
swap(data[depth], data[i]);
}
}
int main(void){
std::vector<int> data={1, 2, 3, 4, 5};
std::vector<std::vector<int>> ret;
permutation(data, ret, 0, data.size(), 3);
for(std::vector<int> set: ret){
for(int s: set) std::cout<<s<<" ";
std::cout<<std::endl;
}
}
next_permutation(vec.begin(), vec.end());
next_permutation을 사용하기 전에 항상 오름차순 정렬을 해주어야 함
결과에서 중복은 제외함
nPn
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
vector<int> v={1, 2, 3};
do{
for(int i=0; i<v.size(); ++i) cout<<v[i]<<" ";
cout<<endl;
} while(next_permutation(v.begin(), v.end()));
}
nPr
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
vector<int> v={1, 2, 3, 4, 5};
int r=2, n=v.size();
do{
for(int i=0; i<r; ++i) cout<<v[i]<<" ";
cout<<endl;
reverse(v.begin()+r, v.end());
} while(next_permutation(v.begin(), v.end()));
}
prev_permutation(vec.begin(), vec.end());
내림차순으로 순열 정렬을 처리
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(int i, int j) {
return j<i;
}
int main(void){
vector<int> v={2, 1, 3};
sort(v.begin(), v.end(), compare);
do{
for(int i=0; i<v.size(); ++i) cout<<v[i]<<" ";
cout<<endl;
} while(prev_permutation(v.begin(), v.end()));
}