[Math] 순열(Permutation) / Java

순열(順列)

순서를 고려해 나열한 경우의 수.

즉, 서로 다른 n개 중 r개를 골라 순서를 정해 나열하는 경우의 수(nPr)를 의미합니다.

예를 들어, 다섯 명의 학생 중 반장 1명과 부반장 1명을 뽑는 경우의 수를 구하는 것이 순열에 해당한다고 볼 수 있습니다.

공식은 다음과 같습니다.

순열 공식

구현

주어진 수의 배열이 1, 2, 3일 때 두 개를 뽑는 순열의 경우의 수를 출력하는 코드입니다.

구현 방식은 두 가지입니다.

1. 재귀와 방문배열을 활용한 방식
2. 비트마스킹을 활용한 방식

// 순열(nPr) - n개의 값 중 r개를 순서대로 뽑는 경우의 수
public class Permutation {

    static int[] arr = {1, 2, 3};
    static int n = arr.length;  // 주어진 수의 갯수
    static int r = 2;  // 뽑을 갯수
    static boolean[] visited = new boolean[n];  // 현재 순열에 특정 값이 포함되었는지 여부
    static int[] output = new int[r];  // 출력할 순열을 저장하는 배열

    public static void main(String[] args) {
        perm(0);
        permWithBit(0, 0);
    }

    // 1. 재귀를 활용한 순열 생성
    static void perm(int depth) {
        if (depth == r) {
            print();
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            visited[i] = true;
            output[depth] = arr[i];  // 출력 배열에 값 저장
            perm(depth+1);  // 재귀
            visited[i] = false;
        }
    }

    // 2. 비트 마스킹을 활용한 순열 생성
    static void permWithBit(int depth, int flag) {
        if (depth == r) {
            print();
            return;
        }

        for (int i = 0; i < n; i++) {
            if ((flag & (1<<i)) != 0 ) continue;  // i번째 원소가 이미 등록된 경우

            output[depth] = arr[i];
            permWithBit(depth+1, flag | 1<<i);  // i번째 원소를 flag에 등록
        }
    }

    static void print() {
        for (int i = 0; i < r; i++) {
            System.out.print(output[i]+ " ");
        }
        System.out.println();
    }

}

 

두 가지 구현방식의 코드 실행결과는 서로 일치하며 그 내용은 다음과 같습니다.

1 2 
1 3 
2 1 
2 3 
3 1 
3 2