순열 (Permutation)

순열 (Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열의 경우의 수는 아래와 같다.
  • nPr = n * (n - 1) * ... * (n - r + 1)
• n이 12 이상일 경우부터 시간 복잡도가 급격히 상승한다.

 

소스코드

import java.util.Arrays;

public class Permutation {
    public static void permutation(int[] arr, boolean[] selected, int depth) {
        if (depth == selected.length) {
            System.out.println(Arrays.toString(arr));
            return;
        }

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

    public static void main(String[] args) {
        permutation(new int[3], new boolean[3], 0);
    }
}

실행결과

 

여기서 point !

- depth 는 몇번째 선택인 지를 나타내는 변수

- i는 그 depth에서 선택가능한 것을 구해주는 변수 => boolean배열 selected로 중복 선택을 피한다.

- return문이 있는 종료조건에 원하는 코드를 짜면 된다.

 

예시)