(C++)순열

순열

서로 다른 n개의 요소에서 r개를 뽑아 순서가 있도록 하나의 배열로 만드는 것

next_permutation

보통 do~while문과 함께 사용하며 순열의 형태로 순서를 바꾸는next_permutation함수는 while문에 들어간다.

do {
    //로직
    } while (next_permutation(first, last, pred));

next_permutation의 매개 변수는 3개가 있으며

1. first는 순열함 범위의 첫 번째 요소 위치의 주소
2. last는 순열할 범위의 마지막 요소 하나 다음위치의 주소
3. 순서에 따라 연속적인 요소에 대해 충족돌 비교 조건 정의

next permutation사용시 주의사항
visualstudio 공식문서의 next_permutation을 보면
원래 순서가 사전적으로 다음으로 큰 순열(있는 경우)으로 대체되도록 범위의 요소를 다시 정렬
반환 값

• true 사전적으로 다음 순열이 존재하고 범위의 원래 순서를 대체한 경우;
• 그렇지 않으면 false순서가 사전적으로 가장 작은 순열로 변환

완전탐색을 하는 경우 배열,벡터,문자열등이 정렬이 되어있지 않다면 sort함수를 통해 오름차순 정렬을 먼저 사용하고 순열을 돌려야 모든 경우의 수가 출력된다. 세번째 매개변수는 커스텀 정렬 할 때 따로 다루겠지만 어떠한 컨테이너 내부의 요소를 어떤 순서로 탐색,변경할지 결정하기 때문에 매우 중요하다. 세번째 매개변수는 생략 했을 때 default로 오름차순 정렬된 경우만 순열을 정렬한다.

예제(커스텀 정렬 내림차순)

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool cmp(int a, int b) {
    return a > b;
}

int main() {

    int a[] = { 3,2,1 };

    do {
        for (auto ele : a) {
            cout << ele << ' ';
        }
        cout << '\n';
    } while (next_permutation(a, a + sizeof(a) / sizeof(int), cmp));




    return 0;
}
//출력
3 2 1 
3 1 2 
2 3 1 
2 1 3 
1 3 2 
1 2 3 

원래 배열이 내림차순으로 있을 경우 3,2,1인 경우 하나만 출력 한다. 하지만 세번째 매개변수를 내림차순으로 정렬을 하도록 비교함수를 만들었기 때문에 모든 경우의 수가 출력된다.

예제(기본값)

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {

    int a[] = {1,2,3 };

    do {
        for (auto ele : a) {
            cout << ele << ' ';
        }
        cout << '\n';
    } while (next_permutation(a, a + sizeof(a) / sizeof(int)));




    return 0;
}
//출력
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

세번째 매개변수를 넣지 않을 경우 기본값으로 오름차순으로 정렬된 경우만 출력

vector

#include<iostream>
#include<vector>
#include<algorithm>
int main() {

    string s = "bca";
    sort(s.begin(), s.end());
    cout << s << '\n';
    do {
        for (auto ele : s) {
            cout << ele << ' ';
        }
        cout << '\n';
    } while (next_permutation(s.begin(),s.end()));

    return 0;
}
//출력
a b c 
a c b 
b a c 
b c a 
c a b 
c b a 

문자열

#include<iostream>
#include<vector>
#include<algorithm>
int main() {

    vector<int> v = { 1,2,3 };

    do {
        for (auto ele : v) {
            cout << ele << ' ';
        }
        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 

재귀함수

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int a[3] = { 2,3,4 };
vector<int> v;

void mkPermutation(int n, int r, int depth) {
    if (depth == r) {
        for (auto ele : v) {
            cout << ele << " ";
        }
        cout << '\n';
    }
    for (int i = depth; i < n; i++) {
        swap(v[i], v[depth]);
        mkPermutation(n, r, depth + 1);
        swap(v[i], v[depth]);
    }
}

int main() {

    for (int i = 0; i < sizeof(a)/sizeof(int); i++) {
        v.push_back(a[i]);
    }

    mkPermutation(v.size(), 3, 0);

    return 0;
}
//출력
2 3 4 
2 4 3 
3 2 4 
3 4 2 
4 3 2 
4 2 3