순열(Permutation) (+Java 코드)

1. 순열(Permutation)이란

순열은 n개의 숫자 중에서 r개를 뽑아야 할 때 순서를 고려해서 뽑는 것을 말합니다.

순서에 따라 결과가 달라지기 때문에 같은 1,2,3 데이터를 사용하더라도 <123,132,213,231,312,321> 은 모두 다른 결과로 취급하게 됩니다.

 

2. 구현 방법

그렇다면 순열은 코드 상에서 어떻게 구현할 수 있을까요?

(1) depth 변수 사용

depth 변수를 통해 깊이를 이동하며 데이터를 뽑는 방식입니다.

depth 변수는 result 배열의 index를 의미하며 현재 뽑고자 하는 데이터의 위치라고 생각해 주시면 됩니다!

 

depth가 0일 때에는 result[0]의 숫자를 결정합니다.

visited 배열을 통해 아직 사용하지 않은 데이터가 있다면 그 데이터들은 모두 result[0]의 후보가 될 수 있습니다. (visited 배열은 중복 방지를 위해 사용하는 것이므로 중복 순열을 구하고 싶다면 visited 배열을 사용하지 않으면 됩니다!)

 

 

depth가 1일 때에는 result[1]의 숫자를 결정하면 됩니다.

 

depth가 2일 때에는 result[2]의 숫자를 결정하면 됩니다.

/**
    * @param arr 숫자를 뽑아낼 배열
    * @param visited 선택 여부를 체크할 배열
    * @param result 선택한 순열의 결과
    * @param depth 선택할 숫자의 순서
    * @param r 뽑고자 하는 숫자의 개수
    */
    static void permutation(int[] arr, boolean[] visited, int[] result, int depth, int r) {
        if(depth == r) {
            print(result);
            return;
        }

        for(int i=0; i<arr.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                result[depth] = arr[i];
                permutation(arr, visited, result, depth+1, r);
                visited[i] = false;
            }
        }
    }

    static void print(int[] result) {
        for(int n: result) {
            System.out.print(n);
        }

        System.out.println();
    }

(2) 결과

참고 https://bcp0109.tistory.com/14 https://java-is-happy-things.tistory.com/6