[완전 탐색] 순열

순열

모든 경우의 수를 탐색하는 방법인 완전 탐색 중의 한 방법이다.

_nP_r로 n개 중에서 r개를 순서 상관있이 고르는 모든 경우의 수이다. r == n이면 n!이다.

 

반복문

다중 for문을 통해 순열을 구할 수 있다. 다만 r이 계속 변화하거나 큰 값이면 복잡해진다.

public class Main {
    public static void main(String[] args) {
        for(int i=1; i<=3; i++){
            for(int j=1; j<=3; j++){
                if(i == j) continue;
                for(int k=1; k<=3; k++){
                    if(i == k || j == k) continue;
                    System.out.println("[" + i + ", " + j + ", " + k + "]");
                }
            }
        }
    }
}

 

재귀함수

재귀함수로 구현하면 r이 변수여도 구현 가능하다.

public class Main {
    public static void main(String[] args) {
        permutation(0);
    }

    static int[] arr = new int[3]; // 순열이 저장되는 배열
    static boolean[] selected = new boolean[3]; // 중복 체크를 위한 배열
    static void permutation(int cnt){
        if(cnt == 3){
            System.out.println(Arrays.toString(arr));
            return;
        }

        for(int i=0; i<3; i++){
            if(selected[i]) continue;
            arr[cnt] = i + 1;
            selected[i] = true;
            permutation(cnt + 1);
            selected[i] = false;
        }
    }
}