next_permutation - Java 구현

Posted by Eun JongHyeok on August 21, 2021
  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 →