permutation(순열) 구현

[순열 이란?]

순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다.
예를들어 [1,2,3] 수열이 있을경우 이에 대한 순열은 다음과 같이 6가지가 있다.

**[1,2,3] 
[1,3,2] 
[2,1,3] 
[2,3,1] 
[3,1,2] 
[3,2,1]**

[next_permutation 알고리즘]

이때 이는 오름차순으로 정렬된 수열에 대하여 내림차순으로 바꾸는 과정에서 다음번째 수열의 과정을 뜻한다.

s{i|0<=i<N}

1. s(수열)에 대해서 s[i-1]<s[i]를 만족하는 가장 큰수를 찾는다.

2. 1번에서 찾은 i-1에 대하여 s[i-1]<s[j]를 만족하는 가장 큰 j를 찾는다

3. s[i-1] s[j]를 바꿔치기한다.

4. s[i..n-1]를 reverse시킨다.

예시) s=[1,4,3,2]

1) i=1, s[i]=4, s[i-1]=1

2) j=3, s[j]=2

3) s[i-1]=1과 s[j]=2를 바꿔치기하면 s=[2,4,3,1]이 된다.

4) [i~n-1]=>[1~3]를 reverse시키면 s= [2,1,3,4]가 된다.

[구현]

void reverse(string &s,int i,int n){
    for(;i<n;) swap(s[i++],s[n--]); 
 }
bool nextPermutation(string& s)
{
    // 1. s(수열)에 대해서 s[i-1]<s[i]를 만족하는 가장 큰수를 찾는다.
    // 2. 1번에서 찾은 i-1에 대하여 s[i-1]<s[j]를 만족하는 가장 큰 j를 찾는다
    // 3. s[i-1] s[j]를 바꿔치기한다.
    // 4. s[i..n-1]를 reverse시킨다.
    int i, j;
    i = j = s.size()-1;
    while (s[i - 1] >= s[i]) if (--i== 0) return false; //1번에 해당하는 i찾기
    while(s[j]<=s[i-1]) if(--j==0) return false; //2번에 해당하는 j찾기
    swap(s[j],s[i-1]);
    reverse(s,i,s.size()-1);
    return true;
}