브루트포스(3) 순열

순열

순열(Purmutation)은 숫자를 사전순으로 나열한 것을 의미한다.

Ex) 1,2,3 순열

1 2 3 -> 시작 순열(오름차순)

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1 -> 끝 순열(내림차순)

순열은 시작지점, 끝지점, 다음 순열,이전 순열로 표현할 수 있다.

시작순열과 끝 순열을 각각 오름차순과 내림차순으로 구성된다.

 

다음 순열

순열의 다음을 구하는 방법이다.

끝순열을 구해서 그 다음 구해주어 해결한다.

private boolean nextPermutation(int[] numbers){
        int prevIndex;
        int n = numbers.length;
        int nextIndex = n-1;
        int changeIndex = -1;

        for(int i = n-2; i >= 0; i--){
            prevIndex = nextIndex;
            nextIndex = i;

            if(numbers[nextIndex] < numbers[prevIndex]){
                changeIndex = nextIndex;
                break;
            }
        }

        if(changeIndex == -1)
            return false;

        for(int i = n-1; i > changeIndex; i--){
            if(numbers[i] > numbers[changeIndex]){
                swap(numbers, i, changeIndex);
                break;
            }
        }
        while(++changeIndex < --n){
            swap(numbers,changeIndex,n);
        }
        return true;
    }

    private void swap(int[] numbers, int a, int b){
        int temp = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = temp;
    }

Ex) 5 3 6 4 2 1

위 순열의 다음 순열은 5 4 1 2 3 6 이다.

위 순열은 5는 고정 뒤 3 6 4 2 1이 변경되어야 함을 알 수 있다.

 

1. 최대한 끝순열 찾기

6 4 2 1까지는 내림차순이므로 끝순열임

3 6 4 2 1 에서 3의 위치를 바꿔주면 됨

 

2. 3과 변경할 적절한 값 찾고 변경

순열은 사전순(3보다 큰 값이 와야함)

6 4 2 1 중 3보다는 크고 제일 작은 값이 와야함.

따라서 4 6 3 2 1이 됨.

 

3. 변경된 위치 이전부터 크로스로 교체 해주기(순열의 시작지점 만들어주기)

6 <-> 1

4 1 3 2 6

3 <-> 2

4 1 2 3 6

이전 순열

다음 순열을 구하는 것에 대하여 부등호를 반대로 하면 된다.

 

시간복잡도

다음 순열을 구하는 시간복잡도 : O(n)