[알고리즘_개념] 재귀를 이용한 순열표현

순열이란?

wiki백과 '순열'의 정의 일부

수학적으로는 완전순열이라고 하는데, 쉽게 말해서 모든 원소의 위치를 바꿔서 주어진 수 배열을 나열할 수 있는 경우의 수를 모두 표현한 것이다.

예를들어, {1, 2, 3} 이라면 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}가 해당된다.

 

순열의 구현

첫번째로 생각해봐야하는 것은 해당 순열의 다음순열 구하기이다. 그래야 loop문으로 모든 순열을 구현할 수 있기 때문!

 

[순열의 다음순열 구하기]

{1 2 3 4 5 6 7}로 이루어진 순열을 사전순으로 나열했을 때, 마지막에 올 수 있는 것은 {7 6 5 4 3 2 1}일 것이다.

앞의 자리가 3이면서 마지막에 올 수 있는 것은 ? {3 7 6 5 4 2 1}

앞의 자리가 4 5이면서 마지막에 올 수 있는 것은 ? {4 5 7 6 3 2 1}

 

구현을 생각하지 않고 {3 7 6 5 4 2 1}의 다음 순열을 생각해봤다.

 1. 바껴야할 것같은 자리수 : 3

 2. 순열의 원소에서 3보다 한단계 큰수를 찾아서 바꾸기 : {3 7 6 5 4 2 1} -> {4 7 6 5 3 2 1}

 3. 바뀐 후, 처음값이니까 왠지 바뀐 자리수인 4를 제외하고 오름차순을 해줘야할 것 같음. : {4 1 2 3 5 6 7}

 4. 구했다. 

{3 7 6 5 4 2 1} -> {4 1 2 3 5 6 7}

 

다음순열 구현

int[] a = {7, 2, 3, 6, 5, 4, 1}; 

 

1 .바껴야 하는 대상 찾기 : 맨 뒤부터 검사해서 감소수열 다음 인덱스 찾기.

 

코드

결과

결과

코드복사는 아래

public class Main {
    static boolean next_permutation(int[] a){
        //맨 뒤 인덱스값을 담은 i
        int i = a.length-1;
        while(i>0 && a[i-1] >= a[i]){
            i -= 1;
        }

        //i==0이라는건 수열 자체가 감소수열이고 사전순으로 봤을 때 다음 값이 없으므로 return false
        if(i <= 0){
            return false;
        }

        // 대상의 인댁스는 i-1이다.
        System.out.println("i-1 : " + (i-1) + ", a[i-1] : " + a[i-1]);
        return true;
    }


    public static void main(String[] args) {
        int[] a = {7, 2, 3, 6, 5, 4, 1};
        next_permutation(a);
    }
}

 

2. 바꿔야할 대상과 (감소순열 중 가장 작은 값 && 대상보다 큰 값)을 swap

 

코드

코드복사는 아래

public class Main {
    static boolean next_permutation(int[] a){
        //맨 뒤 인덱스값을 담은 i
        int i = a.length-1;
        while(i>0 && a[i-1] >= a[i]){
            i -= 1;
        }

        //i==0이라는건 수열 자체가 감소수열이고 사전순으로 봤을 때 다음 값이 없으므로 return false
        if(i <= 0){
            return false;
        }

        // 대상의 인댁스는 i-1이다.
        System.out.println("i-1 : " + (i-1) + ", a[i-1] : " + a[i-1]);

        // i-1과 바꿀 대상을 감소순열에서 고르기 (조건 : a[i-1]보다 큰 값 중에서 감소순열에서 제일 작은 값)
        // 뒤에서부터 감소순열을 탐색할 j값 할당
        int j = a.length-1;
        while(a[i-1] >= a[j]){
            j -= 1;
        }

        // 감소순열중에서 i-1과 바꿀 값 출력
        System.out.println("j : " + j + ", a[j] : " + a[j]);
        return true;
    }


    public static void main(String[] args) {

        int[] a = {7, 2, 3, 6, 5, 4, 1};
        next_permutation(a);
    }
}

결과

 

3. a[i-1]과 a[j]를 swap후, 감소순열에 해당하는 i~맨 뒤 인덱스까지 오름차순으로 정렬해주기

위의 코드에 다음을 추가함.

전체코드는 아래

public class Main {
    static boolean next_permutation(int[] a){
        //맨 뒤 인덱스값을 담은 i
        int i = a.length-1;
        while(i>0 && a[i-1] >= a[i]){
            i -= 1;
        }

        //i==0이라는건 수열 자체가 감소수열이고 사전순으로 봤을 때 다음 값이 없으므로 return false
        if(i <= 0){
            return false;
        }

        // 대상의 인덱스는 i-1이다.
        System.out.println("i-1 : " + (i-1) + ", a[i-1] : " + a[i-1]);

        // i-1과 바꿀 대상을 감소순열에서 고르기 (조건 : a[i-1]보다 큰 값 중에서 감소순열에서 제일 작은 값)
        // 뒤에서부터 감소순열을 탐색할 j값 할당
        int j = a.length-1;
        while(a[i-1] >= a[j]){
            j -= 1;
        }

        // 감소순열중에서 i-1과 바꿀 값 출력
        System.out.println("j : " + j + ", a[j] : " + a[j]);
        
        // a[i-1]과 a[j]를 바꿈
        int tmp = a[i-1];
        a[i-1] = a[j];
        a[j] = tmp;
        
        // i부터 끝까지 오름차순 정렬, i~a.length-1까지의 수열은 감소순열이므로 정렬이 다음과 같이 쉽다.
        j = a.length-1;
        while(i<j){
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
        }

        for(int ai : a){
          System.out.println(ai + " ");
        }
        
        return true;
    }
    public static void main(String[] args) {

        int[] a = {7, 2, 3, 6, 5, 4, 1};
        next_permutation(a);
    }
}

결과

다음순열 완료!

 

[주어진 배열의 사전순으로 된 순열 구하기]

수열의 처음 값을 기준으로 계속 다음수열, 다음수열, ...., 맨 끝에 나오는 수열 이렇게 !

아래는 7자리수인 {1, 2, 3, 4, 5, 6, 7}의 순열을 사전순으로 나타낸 것의 코드이다.

 

코드

public class Main {
    static boolean next_permutation(int[] a){
        //맨 뒤 인덱스값을 담은 i
        int i = a.length-1;
        while(i>0 && a[i-1] >= a[i]){
            i -= 1;
        }

        //i==0이라는건 수열 자체가 감소수열이고 사전순으로 봤을 때 다음 값이 없으므로 return false
        if(i <= 0){
            return false;
        }

        // 대상의 인댁스는 i-1이다.
        // System.out.println("i-1 : " + (i-1) + ", a[i-1] : " + a[i-1]);

        // i-1과 바꿀 대상을 감소순열에서 고르기 (조건 : a[i-1]보다 큰 값 중에서 감소순열에서 제일 작은 값)
        // 뒤에서부터 감소순열을 탐색할 j값 할당
        int j = a.length-1;
        while(a[i-1] >= a[j]){
            j -= 1;
        }

        // 감소순열중에서 i-1과 바꿀 값 출력
        // System.out.println("j : " + j + ", a[j] : " + a[j]);

        // a[i-1]과 a[j]를 바꿈
        int tmp = a[i-1];
        a[i-1] = a[j];
        a[j] = tmp;

        // i부터 끝까지 오름차순 정렬, i~a.length-1까지의 수열은 감소순열이므로 정렬이 다음과 같이 쉽다.
        j = a.length-1;
        while(i<j){
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
        }

        return true;
    }


    public static void main(String[] args) {

        int[] a = {1, 2, 3, 4, 5, 6, 7};

        do{
            for(int ai : a){
                System.out.print(ai + " ");
            }
            System.out.println();

        }while(next_permutation(a));
    }
}