Next Permutation

Permutation(순열)은 프로그래밍에서 흔하게 사용되는 개념이다. 나무 위키에는 다음과 같이 정의되어 있다.

서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다.

위의 순열의 개념에서 "순서에 상관있게"를 "순서에 상관없게"로 바꾼 개념이 바로 조합(Combination)이다. n과 r이 일정한 수로 주어졌을 때, 어느쪽이 경우의 수가 더 많이 도출될까? 당연하게도, 순열이 그 경우의 수가 훨씬 많다. 

 

$_nP_r = n \times(n-1) \times (n-2) \times ... (n-r+1) =$ $n!\over(n-r)!$

 

$_nC_r = $ $_nP_r\over r! $ = $1\over r!$ $n!\over(n-r)!$

 

 그렇다면, 어느쪽이 더 많은 구현이 필요할까? 조합은 그 가짓수가 많지 않아 구현이 좀더 간단한 반면, 순열은 가짓수가 많아서 구현이 복잡한 경우가 많아서 BruteForce 문제와 같이 모든 경우의 수를 탐색하는 경우에서 많이 사용된다. 어차피 전탐색의 경우에는 1억 연산을 넘어가기 어려워 n이 10 내외로 정해지는 경우가 많아 순열을 만들어 낼 수 있다면 재귀적인 dfs 문제에서도 재귀적으로 연산을 구현하지 않고도 문제를 해결할 수 있는 수단이 생기게 된다. 또한 아래에서 소개할 코드는 배열에 동일한 수가 들어있는 상황(중복 원소)에서도 잘 작동하니 참고하자.

 아래 코드를 보면서 어떤 순서로 구현이 되는지 살펴보자. 

 <전제>

next_permutation(순열)은 내부의 숫자가 오름차순으로 정렬되어 있는 상태에서 내림차순으로 정렬되는 방향으로 진행된다. 

 

<순서>

 예시 원본 배열 : arr = [1, 3, 5, 4, 2]

 PHASE 1) permutation을 수행할 array의 마지막 원소(i)에서부터 앞으로 진행하되, i보다 하나 앞선 i-1의 원소가 i보다 크거나 같다면 계속 탐색, 아래의 예시에서는 i=2일 때 정지하게 됨, arr[i-1] < arr[i] 

  * 탐색 조건에 의해서 i의 위치에서 부터 arr의 마지막까지는 내림차순 정렬된 상태

종료조건) 맨앞의 원소까지 진행하면(i=0) 내림차순으로 정렬이 완료되었으므로, 종료한다. 

 PHASE 2) 다시 또다른 index j로 맨마지막에서부터 탐색하되 이번에는 i-1 번째 값보다 작거나 같으면 계속 탐색한다. 아래의 예시에서는 j = 3 일때 arr[i-1] < arr[j]가 되어 탐색 종료

 PHASE 3) i-1의 값과 j의 값을 switching 한다.

 PHASE 4) j index를 다시 배열의 맨 마지막에 위치 시킨 상태에서 i=j가 될때까지 i는 1씩 증가, j는 1씩 감소 시키면서 값을 switching 시킨다. 이 동작은 i 보다 뒤의 인덱스 전체에 대해서 내림차순 정렬을 다시 오름 차순으로 바꿔주는 역할을한다. 

 PHASE 4까지 순조롭게 진행한다면, true를 리턴하여 next permutation을 진행할 수 있음을 표시한다. 

 

next permutation 작동 예시

 

코드를 보면 좀더 쉽게 이해할 수 있을지 모르겠다. 이해가 어렵다고 생각되면 이런식의 방법에 익숙해 지도록 노력해 보는 것이 좋다. 

bool next_permutations(vector<int> &arr) {
    // 처음 순열은 오름차순, 마지막 순열은 내림차순
    int n = arr.size(); // arr size
    int i = n-1;
    //i>0 이면서 array의 역순으로 차례로 돌면서 뒤의 원소보다 앞의 원소가
    // 작을 때까지 진행 (switching 첫 원소)
    while(i>0 && arr[i-1] >= arr[i]) i -= 1;
    if (i<=0) return false; // 내림차순 정렬되면 false return 종료
    int j = n-1;
    // j 변수를 n-1부터 시작해서 a[i-1]보다 클 때까지 앞으로 진행 (switching 두번째 원소)
    while (arr[j] <= arr[i-1]) j-= 1;
    swap(arr[i-1], arr[j]);
    // i부터 끝까지 수의 순서를 뒤집는다. 초반에 i의 선정이 내림 차순 확인하며
    // 내려오기 때문에 다시 오름차순으로 만드는 과정 
    j = n-1;
    while (i <j) {
        swap(arr[i], arr[j]);
        i += 1; j -= 1;
    }
    return true;
}

 

next_permuation을 구현하고 실제의 문제에서는 아래와 같이 arr의 배열을 오름차순으로 정렬한 상태에서 do while문을 이용해서 next_permutation이 가능한 범위에서 모든 경우를 탐색하는 코드를 구현한다. 

 

sort(arr.begin(), arr.end());

do {
        ans = max(ans, calc(arr));
    } while(next_permutations(arr));

 

여기에 몇가지 변형이 존재할 수 있다. next_permutation이 오름차순을 내림차순으로 바꾸어가며 전체 탐색을 진행한다면 반대로 내림차순을 오름차순으로 바꾸어가며 탐색할 수도 있지 않을까? 이 구현은 비교적 simple하게 구현이 가능한데, 바로 PHASE I과 PHASE II의 부호만 반대로하면 구현이 가능하다. 

 

bool prior_permutations(vector<int> &arr) {
    // 처음 순열은 내림차순, 마지막 순열은 오름차순
    int n = arr.size(); // arr size
    int i = n-1;
    //i>0 이면서 array의 역순으로 차례로 돌면서 뒤의 원소보다 앞의 원소가
    // 클 때까지 진행 (switching 첫 원소)
    while(i>0 && arr[i-1] <= arr[i]) i -= 1;
    if (i<=0) return false; // 내림차순 정렬되면 false return 종료
    int j = n-1;
    // j 변수를 n-1부터 시작해서 a[i-1]보다 작을 때까지 앞으로 진행 (switching 두번째 원소)
    while (arr[j] >= arr[i-1]) j-= 1;
    swap(arr[i-1], arr[j]);
    // i부터 끝까지 수의 순서를 뒤집는다. 초반에 i의 선정이 내림 차순 확인하며
    // 내려오기 때문에 다시 오름차순으로 만드는 과정 
    j = n-1;
    while (i <j) {
        swap(arr[i], arr[j]);
        i += 1; j -= 1;
    }
    return true;
}

 

또한, 위의 예시처럼 오름차순 또는 내림차순이 완료되면 종료되어 false를 return하는 bool 형의 함수가 아니라 무한히 순환적으로 순열을 만들어내는 함수도 아래와 같이 구현이 가능하다. 

 

void ns_next_permutations(vector<int> &arr) {
    // 처음 순열은 오름차순, 마지막 순열은 내림차순
    int n = arr.size(); // arr size
    int i = n-1;
    //i>0 이면서 array의 역순으로 차례로 돌면서 뒤의 원소보다 앞의 원소가
    // 작을 때까지 진행 (switching 첫 원소)
    while(i>0 && arr[i-1] >= arr[i]) i -= 1;
    if (i<=0) {
        reverse(arr.begin(), arr.end()); // 내림차순 정렬되면 전체 오름차순으로 변경
        return;
    } 
    int j = n-1;
    // j 변수를 n-1부터 시작해서 a[i-1]보다 클 때까지 앞으로 진행 (switching 두번째 원소)
    while (arr[j] <= arr[i-1]) j-= 1;
    swap(arr[i-1], arr[j]);
    // i부터 끝까지 수의 순서를 뒤집는다. 초반에 i의 선정이 내림 차순 확인하며
    // 내려오기 때문에 다시 오름차순으로 만드는 과정 
    reverse(arr.begin()+i+1, arr.end());
}

 

알고리즘 문제를 풀다보면 위의 순열이 꼭 필요한 순간이 올 때가 있다. 위의 코드를 활용하면 재귀적으로 접근하지 않는 좋은 방법이 될 것이다. 알고리즘 문제의 풀이를 위해 주로 Backjoon을 애용하는 편이지만, 문제 풀이가 아닌 실제적인 코드 작성은 leetcode가 뛰어나다는 생각을 많이 한다. 꼭 문제 풀이 뿐만 아니라 실제적으로 현업의 PJT에 코드를 구현해 넣는 듯한 코드 구현이 필요하기 때문이다. 아래를 참고하기 바란다. 

 

<leetcode next_permutation 구현 문제> https://leetcode.com/problems/next-permutation/

Next Permutation - LeetCode

<C++ next_permutation 구현> https://github.com/Koo82/Algotirhm/blob/main/%5BBasic%5Dnext_permutation.cpp

GitHub - Koo82/Algotirhm