순열

순열 함수 next_permutation 이 있고 이를 구현해보겠다.

일단 순열을 구할려면

1.a[i-1]<a[i] 를 만족하는 가장 큰 i를 찾는다.

2.j>=i이면서 a[j]>a[i-1]를 만족하는 가장 큰 j를 찾는다.

3.a[i-1]과 a[j]를 스왑 한다.

4.a[i]부터 순열을 뒤집는다.

 

예를 들어 

7 2 3 6 5 4 1 이 있다. 여기서 1번 과정을 거치면

7 2 3 6 5 4 1   3이 가장 큰 i가 된다.그리고 2번 과정을 거치면

7 2 3 6 5 4 1  4가 가장 큰 j가 된다. 그리고 스왑하면

7 2 4 6 5 3 1   이 되고 여기서 4번 과정을 거치면

7 2 4 1 3 5 6    가 되면서 7 2 3 6 5 4 1 의 다음 순열이 된다.

 

코드를 보자

#include <iostream>
using namespace std;
void swap(int &a,int &b){      //참조에 위한 호출
    int temp=a;
    a=b;
    b=temp;
}
bool next_permutation(int *a , int n){
    int i=n-1;
    while(i>0 && a[i-1]>=a[i])i-=1;         //뒤에서 부터 내림차순이 아니게 될 때를 구함
    if(i<=0) return false;                  //없으면 순열의 끝
    int j=n-1;
    while(a[j]<=a[i-1]) j-=1;               //다시 뒤에서 부터 내림차순 아니게 될떄 까지 반복하며 값이 더 클 때 까지 반환
    swap(a[i-1],a[j]);                      //바꿔줌
    j=n-1;
    while(i<j){
        swap(a[i],a[j]);                   //남은 거도 오름차순이 되게 다 바꿔줌
        i+=1;j-=1;
    }
    return true;
}