본문 바로가기
C_C++ 프로그래밍/C_C++ 프로그래밍

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

by RoJae 2019. 3. 16.


next_permutation => 직역하자면, 다음 수열이라는 의미입니다.


STL에서 제공하는 함수이며 vector, 배열로 구현이 가능합니다.


// 사전 순으로 정렬

1 3 4 2 의 다음 수열은 1 4 2 3 이 됩니다.

이때 1 4 2 3 을 만들기 위해서 4가지 단계를 거치는데


1. 어디까지가 감소 수열인가 찾기.

1 3 4 2 (감소 수열 4 2) 

이떄 i = 2


2. i-1보다 작거나 같으며, 가장 뒤에 있는 수 j 를 찾기

1 3 4 2 (2보다 작으며, 가장 앞에 있는 수를 찾습니다)

이때 j = 3 (2를 가르킵니다)의 이전 인덱스 j = 2( 4를 가르킵니다)


3.  그 둘을 Swap 시킵니다.

1 4 3 2


4.  i -1 이후로 뒤집습니다.

1 4 2 3



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<vector>
 
using namespace std;
 
bool next_permutation(int *a, int n){
    int i = n-1;                    // 뒤부터 시작 
    while(i > 0 && a[i] <= a[i-1])  // 어디까지가 감소수열인가?? 
        i -= 1;
    if(i <= 0)                    // 전체가 감소수열이다. 
        return false;                // 다음 수열은 존재하지 않는다.
    int j = n-1;
    while(a[i-1>= a[j])                
        j -= 1;            
    swap(a[i-1],a[j]);                // 찾은 수의 바로 앞 swap i-1 
    j = n - 1;                     // j는 마지막 
    while(i < j){                    // i-1 이후로, swap해줌 
        swap(a[i],a[j]);
        i +=1;
        j -=1;
    }
    return true;
}
 
int main(){
    int n;
    cin >> n;
    
    int *= new int[n];
        
    for(int i = 0; i < n; i++)
        v[i] = i+1;
        
    do{
        for(int i = 0; i < n; i++)
            cout << v[i] << ' ';
        cout << '\n';
    }while(next_permutation(v,n));
    
    return 0;
}

cs


C++의 STL에서 제공하는 함수도 존재합니다.

간단하게 사용하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(){
    vector<int> a;
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }
    
    do{
        for(int i = 0; i < n; i++)
            cout << a[i];
        cout << '\n';        
    }while(next_permutation(a.begin(), a.end()));
    
    return 0;
}
cs


※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.

'C_C++ 프로그래밍 > C_C++ 프로그래밍' 카테고리의 다른 글

[C++] 선택정렬(Selected Sort)  (0) 2019.04.01
[C++] pair sort  (0) 2019.03.21
[C++] 2차원 동적 배열 생성  (0) 2019.03.19
[Algorithm] C++ Bitmask란?  (0) 2019.03.17

댓글