순열과 순열의 코드 구현 [Java]

순열

- 순열 : n개의 값 중에서 r 개의 숫자를 모든 순서대로 뽑는 것을 말한다.

 

ex) [1, 2, 3] 이라는 3개의 배열에서 2개의 숫자를 뽑는 경우 -> 총 6개이다.

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

swap을 이용한 순열

- swap 함수를 활용하여 배열들의 값을 직접 바꾸는 방법이다.

- 배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 swap 한다.

- depth 를 기준으로 depth 보다 인덱스가 작은 값들은 그대로 고정하고, 큰 값들만 들고 다시 swap을 진행한다.

 

swap을 이용한 순열[코드 구현]

    //순서 상관 없이 n 개중에 r개를 뽑는 경우
    //ex. permutation(arr, 0, 4, 2);	//4개 중 2개를 뽑는 경우
 public class Permutation {
    public static void main(String[] args) {
    	int n = 3;
        int[] arr = {1, 2, 3};
        int[] output = new int[n];
        boolean[] visited = new boolean[n];
        
        perm(arr, output, visited, 0, n, 3);
        System.out.println();
        permutation(arr, 0, n, 3);
    }
    
    public void permutation(int[] arr, int depth, int n, int r) {
        if (depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.println(arr[i] + " ");
            }

            return;
        }

        for (int i = depth; i < arr.length; i++) {
            swap(arr, i, depth);
            permutation(arr, depth + 1, n, r);
            swap(arr, i, depth);
        }

    }
    
    //swap 함수
    public void swap(int[] arr, int depth, int i) {
        int temp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = temp;
    }    
}

visited를 이용한 순열

- swap 함수를 이용한 순열과 달리 visited 배열은 "사전식" 으로 순열을 구현할 수 있다.

변수	설명
arr	r 개를 뽑기 위한 n 개의 값
output	뽑힌 r 개의 값
visited	중복해서 뽑지 않기 위해 체크하는 값

- DFS로 돌면서 모든 인덱스를 방문하여 output에 값을 넣는다.

- 이미 들어간 값은 visited = true로 변경하여 중복 확인한다.

- depth 값은 output에 들어간 숫자의 길이라고 생각하면 된다.

- depth의 값이 r 만큼 되면 output에 들어가있는 값을 출력하면 된다.

visited를 이용한 순열[코드 구현]

// 순서를 지키면서 n 개중에서 r 개를 뽑는 경우
// 사용 예시: perm(arr, output, visited, 0, n, 3);

public class Permutation {
    public static void main(String[] args) {
    	int n = 3;
        int[] arr = {1, 2, 3};
        int[] output = new int[n];
        boolean[] visited = new boolean[n];
        
        perm(arr, output, visited, 0, n, 3);
        System.out.println();
        permutation(arr, 0, n, 3);
    }
    
    static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
        if (depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.println(arr[i] + " ");
            }
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i] != true) {
                visited[i] = true;
                output[depth] = arr[i];
                perm(arr, output, visited, depth + 1, n, r);
                visited[i] = false;
            }
        }
    }
}