next_permutation - Java 구현

Posted by Eun JongHyeok on August 21, 2021
Algorithm 다른 글 보기
  1. 개요
  2. 직접 구현
  3. 느낀점
  4. Reference

오랜만에 알고리즘에 대해 나름 새롭게 정리해보기 위해 작성하는 글입니다. 내용과 원리보다는 구현에 치중되어 있을 수 있으니 자세한 원리는 따로 찾아보는게 좋을거 같습니다.

개요

C++은 STL에서 next_permutation이라는 함수를 제공해주고 있어 순열 문제에 사용했었는데 다른 언어에는 이런 함수가 없다는걸 알게 되어 구현 방법에 대해 고민해 보게 되었습니다.

직접 구현

과거 글에서도 작성했던 내용입니다.

next_permutation의 내부 코드(C++)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25



template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;    // 벡터에 원소가 없을 경우
    BidirIt i = last;
    if (first == --i) return false;     // 벡터에 원소가 하나일 경우
 
    while (true) {
        BidirIt i1, i2;
 
        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

그 때 당시에는 동작에 대해서만 확인해보았는데 다른 언어로 구현을 찾아보게 되면서 의미를 알게 되었습니다.

  1. 가장 긴 감소하는 접미사과 그 pivot(접미사 앞의 위치)를 찾는다.
  2. 가장 긴 감소하는 접미사가 전체 배열일 경우 next_permutation은 없다.
  3. pivot 보다 큰 수 중 가장 오른쪽에 있는 위치(후임)를 찾는다.
  4. pivot과 후임을 스왑한다.
  5. 접미사를 뒤집는다.

다른 예제를 참고하여 구현한 코드입니다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70



import java.util.*;
public class Test {
    private static int[] swap(int data[], int left, int right)
    {
        int temp = data[left];
        data[left] = data[right];
        data[right] = temp;

        return data;
    }

    private static int[] reverse(int data[], int left, int right)
    {
        while (left < right) {
            swap(data, left, right);
            left++;
            right--;
        }

        return data;
    }

    public static boolean next_permutation(int[] data) {
        // 0. 비어있거나 원소가 한개일 경우 next_permutation 없다.
        if (data.length <= 1)
            return false;

        // 1. 가장 긴 감소하는 접미사과 그 pivot(접미사 앞의 위치)를 찾는다.
        int pivot = data.length - 2;
        while (pivot >= 0 && data[pivot] >= data[pivot + 1]) {
            pivot--;
        }

        // 2. 가장 긴 감소하는 접미사가 전체 배열일 경우 next_permutation 없다.
        if (pivot < 0) {
            return false;
        }

        // 3. pivot 보다 큰 수중 가장 오른쪽에 있는 위치를 찾는다.
        int successor = data.length - 1;
        while (data[successor] <= data[pivot]) {
            successor--;
        }

        // 4. pivot과 successor를 스왑한다.
        swap(data, pivot, successor);

        // 5. 접미사를 뒤집는다.
        reverse(data, pivot + 1, data.length - 1);

        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int[] data = new int[k];
        for (int i = 0; i < k; i++) {
            data[i] = sc.nextInt();
        }

        if (next_permutation(data)) {
            System.out.println(Arrays.toString(data));
        } else {
            System.out.println("There is no higher"
                    + " order permutation "
                    + "for the given data.");
        }
    }
}

느낀점

다음 순열을 구해서 해결해야할 경우를 제외하고는 굳이 사용할꺼 같지는 않습니다.

순열을 모두 출력하거나 모든 순열을 탐색할때는 백트래킹을 통해 구현할 것 같습니다.

Reference

https://www.geeksforgeeks.org/implementing-next_permutation-in-java-with-examples/

Permutation
Java
Next Post →