순열 알고리즘 (Permutation Algorithm) - Java

순열이란 n 개의 값에서 r 개의 숫자를 모든 순서대로 뽑는 경우를 말한다.

예를 들어 [1,2,3]이라는 3개의 배열에서 2개의 숫자를 뽑는 경우는

1,2
1,3
2,1
2,3
3,1
3,2

이렇게 6개가 된다

순열 알고리즘은 swap를 활용한 방법과 DFS를 활용한 방법 두가지가 있는데 여기서는 DFS를 활용한 방법에 대해 설명하겠다.

DFS를 활용한 순열

DFS를 활용한 방법은 사전식으로 순열을 구현할 수 있다.

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

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

이미 들어간 값은 visited에 true 처리를 하여 다음에 중복으로 들어가지 않도록 한다.

depth 값은 output에 들어간 숫자의 길이고
depth 의 값이 r 만큼 되면 중단하고 output를 출력하면 된다.

public static void perm(int[] arr, int[] output, boolean[] visited,int depth, int n, int r) {
        if(depth == r) { //만약 depth가 r이면 중단
            list.add(output);
            return;
        }

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

먼저 중단점 먼저 설정을 해주어야 한다.
depth값이 만약 r 값이랑 일치할 때 중단하는 것으로 중단점을 설정해준다.

if(depth == r) { //만약 depth가 r이면 중단
            list.add(output);
            return;
        }

이후 for 문을 돌면서 visted[i]에서 들렀는지 확인을 하면서 순열을 완성시킨다.

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

전체 코드

public class Permutation{
   static List<int[]> list = new ArrayList<>();
   public static void main(String[] args) {
       int n = 5; //임의로 설정
       int[] arr = {1,2,3}; //임의로 설정
       int[] output;
       boolean[] visited = new boolean[n];

       for(int i = 1; i<=arr.length; i++) { 
           output = new int[i];
           perm(arr, output, visited, 0, n, i);
       }
   }

   public static void perm(int[] arr, int[] output, boolean[] visited,int depth, int n, int r) {
       if(depth == r) { //만약 depth가 r이면 중단
           list.add(output);
           return;
       }

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