next_permutation

#include <stdio.h> 

#define SWAP(X,Y) { int T=X; X=Y; Y=T; } 

// 일반꼴로 n개 중에서 r개를 택하여 순서대로 늘어놓는 경우의 수를 모두 출력해 준다.

// 주어진 n, r의 값에 따라서 permutation을 초기화 해준다.

void init_permutation(int a[], int n, int r); 

// 현재 주어진 permutation 으로 부터 바로 다음 permutation을 구한다.

int next_permutation(int a[], int n, int r); 

int main() { 

    // permutation을 담을 정수배열

    int a[100]; 

    // n, r이외에 변수 i를 사용한다.

    int i, n, r; 

    // n을 입력받는다.

    printf("Enter n: "); 

    scanf("%d", &n);

    // r을 입력받는다.

    printf("Enter r: ");

    scanf("%d", &r); 

    // 앞의 r개 까지는 1부터 r까지의 값을 넣어 주고,

    // 뒤의 n-r개에 대해서는 n부터 n-r+1까지의 값을 꺼꾸로 넣어준다.

    // 뒤 부분은 영향을 미치지 않고 다음 permutation 으로 갈 수 있도록 해주는 것이다.

    init_permutation(a, n, r); 

    do { 

        // 현재 벡터를 출력한다. 

        // 앞부분의 r개를 출력해 준다.

        printf("{"); 

        for(i=0;i<r;i+=1) { 

            printf("%d", a[i]); 

            if(i<r-1) putchar(','); 

         } 

         printf("}\n"); 

    // 다음 permutation이 존재하는 동안 계속해서 다음 permutation을 구해 준다.

    } while(next_permutation(a, n, r));

    return 0; 

} 

// permutation을 초기화 해준다.

// 앞부분의 r개는 1부터 r까지의 값을 순서대로 넣어주고,

// 뒷부분은 n부터 n-r+1까지의 값을 꺼꾸로 넣어준다.

// 이렇게 꺼꾸로 넣어주는 이유는 같은 앞부분을 가지는 순열들 중에서

// 마지막 순서이기 때문에 다음 순서를 구하면 제대로 구해지기 때문이다.

void init_permutation(int a[], int n, int r) { 

    int i; 

    for(i=0;i<r;i+=1) { 

        a[i]=i+1; 

    } 

    for(i=r;i<n;i+=1) { 

        a[i] = n+r-i; 

    } 

} 

// 현재의 순열로 부터 바로 다음에 나오는 순열을 구해내는 함수이다.

// 아이디어는 뒤에서 부터 앞쪽으로 가면서 증가하는 (감소하지 않는) 부분으로만

// 순열이 되어있다면 이 순열이 가장 마지막 순열이라는 것이다.

// 앞부분+뒷부분 에서 뒷부분이 증가하지 않는 부분이고, 이에 속하지 않는 앞부분이

// 1 2 3 4 5 의 경우 [1 2 3 4] [5] 로 쪼개진다.

// 4와 5를 바꾸어 주면 [1 2 3 5] [4] 가 되어서 다음에 오는 순열이 된다.

// [1 2 3] [5 4]의 다음에 나오는 순열은 3보다 큰 수를 뒷부분의 뒤에서 부터 찾아서

// 처음 찾은 4와 3을 바꾸어 준다.

// [1 2 4] [5 3] 이 때 뒷부분을 역순으로 바꾸어 주어야 다음 순열이 구해진다.

// [1 2 4] [3 5] 

// [1 2 4 3] [5]의 다음에 나오는 순열은 3보다 큰 5를 찾아서 바꾸어 준다.

// [1 2 4 5] [3]

// [1 2 4] [5 3]의 다음에 나오는 순열은 4보다 큰 5를 찾아서 바꾸어 준다.

// [1 2 5] [4 3] 이 때 뒷부분을 역순으로 바꾸어 주어야 다음 순열이 구해진다.

// [1 2 5] [3 4]

// [1 2 5 3] [4] 

// ..... 생략

int next_permutation(int a[], int n, int r) { 

    int i; 

    int maxk=-1; 

    int maxs, s; 

    // n 안에서 가장 큰 숫자를 찾는다.  (order가 바뀌지 않는) 

    for(i=0;i<n-1;i+=1) { 

        if(a[i]<a[i+1]) maxk=i; 

    } 

    if(maxk==-1) return 0; 

    // 가장 큰 숫자와 나머지 다른 곳에서 더 큰 숫자가 있는지 검사한다. 

    maxs = maxk+1; 

    for(i=maxs+1;i<n;i+=1) { 

        if( a[maxk]<a[i]) maxs=i; 

    } 

    SWAP(a[maxk], a[maxs]); 

    // 나머지 부분을 역순으로 바꾼다. 

    s = n-maxk-1;  

    for(i=0;i<s/2;i+=1) { 

        SWAP(a[maxk+1+i], a[maxk+s-i]); 

    } 

    // r 이후의 부분을 역순으로 바꾼다. 

    s=n-r; 

    for(i=0;i<s/2;i+=1) { 

        SWAP(a[r+i], a[r+s-i-1]); 

    } 

    return 1;  

}