다음 순열 찾기 / 전체 순열 탐색 알고리즘 (Next Permutation)

순열탐색은 알고리즘 문제풀이나 실제 코딩에서도 상당히 많이 등장하는 알고리즘의 한 종류이다.

가령 명확한 기준을 갖고 일정한 순서로 전체를 탐색해야 하는 경우, 매우 유용하게 쓰일 수 있으며, 면접에서도 종종 등장하는 알고리즘 구현 문제이다.

순열 탐색을 하는 데 있어서 방법은 많은데, 포스팅에서 다룰 유명한 알고리즘이 있고, 이 방법을 모른다면 일반적으로 DFS나 BFS 를 이용해서도 구현할 수 있다. 하지만 많은 경우에 있어서 구현이 쉽지 않을 것이다.

이번에 다룰 알고리즘은 O(N) 의 시간복잡도로, 무작위 순열의 다음 순열을 구해내는 알고리즘이다.

또한 이를 바탕으로 무작위로 배치된 전체 수열의 모든 순열의 쌍을 구해보고자 한다.

모든 수열의 쌍을 구하는 알고리즘은 무작위 순열의 다음 순열을 구해낸다면 똑같이 적용하면 되므로, 다음 순열을 구하는 Next Permutation Algorithm 부터 정리해보자. 먼저 다음과 같은 수열을 예로 들어보자.

제시된 수열 N은 무작위의 5개 숫자를 갖고 있다. 이 때, 이 순열의 다음 순열을 구하고자 하면 상당히 난감하다. 전체를 탐색하는 알고리즘이 보통 먼저 떠오를텐데, 이는 개별 순열에 대해서는 굉장히 비효율적이다. 

(해당 알고리즘을 모듈화한다고 생각해보자. 함수에서 해당 모듈을 사용할 때마다 전체를 탐색할 수는 없는 일이다!)

Next Permutation 알고리즘은 다음과 같은 Greedy 방법으로 쉽게 다음 순열을 도출해낸다.

먼저, 순열의 전체를 순회하면서(O(n)) N[i] < N[i+1] 인 가장 마지막 i 를 구해낸다. 위의 예시에서 N[i] < N[i+1] 인 i 는 2개가 있지만, 가장 뒷번호의 인덱스를 가진 i 는 2이다. 만약 이때 i가 존재하지 않는다면, 해당 순열이 가장 마지막 순열이 된다.

그 다음에는 배열의 끝부터 좀전에 구해낸 i 까지 오면서 N[j] > N[i] 인 위치, 즉 N[i] 보다 큰 가장 마지막 Element 를 찾아내고, 이 위치를 J 라고 정한다. 이때, Greedy 알고리즘이 사용되는데, 좀 전 단계에서 N[i] < N[i+1] 인 위치를 찾고 i라고 정했기 때문에, J는 무조건 존재한다.  O(n)

다음에는 N[i] 와 N[j] 를 서로 스왑(Swap)해주자. O(1)

이제 남은 단계는 하나다. i+1부터 수열의 마지막까지 Reverse 해주면 된다. Reverse 한다는건, {1, 2, 3} 이라고 저장되어 있을 때 {3, 2, 1} 로 바꾸어 주면 된다는 뜻이다.

이렇게 나온 순열이 초기 순열(2, 5, 1, 9, 7)의 다음 순열이 된다. 간단하지 않은가. 이를 Java 코드로 옮겨보았다.

    /**

     * Find Next Permutation

     *

     * @param nums

     * @return

     */

    private int[] nextPermute(int[] nums) {

        int[] copies = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {

            copies[i] = nums[i];

        }

        int idx = -1;

        for (int i = 0; i < copies.length - 1; i++) {

            if (copies[i] < copies[i + 1]) {

                idx = i;

            }

        }

        if (idx < 0) {

            //Last Permutation

            return null;

        }

        for (int i = copies.length - 1; i > idx; i--) {

            if (copies[idx] < copies[i]) {

                int tmp = copies[idx];

                copies[idx] = copies[i];

                copies[i] = tmp;

                break;

            }

        }

        for (int i = idx + 1; i < (copies.length + idx + 1) / 2; i++) {

            int tmp = copies[i];

            copies[i] = copies[copies.length - (i - idx)];

            copies[copies.length - (i - idx)] = tmp;

        }

        return copies;

    }

위의 코드에서 idx가 예시의 i를 의미한다. 이를 이용하면 다음 순열을 O(N) 의 복잡도로 구할 수 있다. 이를 전체 순열 탐색에도 적용해보자.

    /**

     * Find Next Permutation

     *

     * @param nums

     * @return

     */

    private int[] nextPermute(int[] nums) {

        int[] copies = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {

            copies[i] = nums[i];

        }

        int idx = -1;

        for (int i = 0; i < copies.length - 1; i++) {

            if (copies[i] < copies[i + 1]) {

                idx = i;

            }

        }

        if (idx < 0) {

            //Last Permutation

            return null;

        }

        for (int i = copies.length - 1; i > idx; i--) {

            if (copies[idx] < copies[i]) {

                int tmp = copies[idx];

                copies[idx] = copies[i];

                copies[i] = tmp;

                break;

            }

        }

        for (int i = idx + 1; i < (copies.length + idx + 1) / 2; i++) {

            int tmp = copies[i];

            copies[i] = copies[copies.length - (i - idx)];

            copies[copies.length - (i - idx)] = tmp;

        }

        return copies;

    }

    /**

     * Find All Permutation

     *

     * @param nums

     * @return

     */

    public List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> permutations = new ArrayList<>();

        Arrays.sort(nums);

        int[] curArray = nums;

        while (true) {

            List<Integer> integerList = new ArrayList<>();

            for (int i = 0; i < curArray.length; i++) {

                integerList.add(curArray[i]);

            }

            permutations.add(integerList);

            int[] nextPermutation = nextPermute(curArray);

            if (nextPermutation == null) {

                break;

            }

            curArray = nextPermutation;

        }

        return permutations;

    }

이제, permute 함수를 이용하면 무작위로 전달된 수열의 전체 순열을 순서대로 뽑아낼 수 있다. 결과가 많기 때문에 예시의 결과만 확인해보자.

Permute 함수의 결과로 나온 2차원 List 를 출력한 모습이다. 초기에 제시된 순열의 다음 순열을 성공적으로 구해내는 것을 확인할 수 있다.

Permute 함수는 아니겠으나, nextPermute 함수의 Next Permutation 알고리즘이 사용하는 방식은 C++ 의 STL 이 사용하는 수도코드와 같다. 최적화된 Greedy 알고리즘으로 생각된다. 좀 더 연구가 하고 싶다면 다음 자료를 참조하자.

(https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order)

순열의 순차탐색은 많이 사용하는 알고리즘이지만, 면접이나 코딩테스트와 같은 제한된 환경에서 최적화된 시간 복잡도를 요하는 바로 다음 순열을 구하기는 쉽지 않다.

어려운 알고리즘이 아니기 때문에 이해하고 외워두는 것도 좋다.