순열 이란?

서로 다른 n개의 원소 중 r개를 고르는 것을 순열이라 한다. nPr로 그 경우의 수를 나타낸다.

permutation.png

단순한 순열 제작

for를 중첩하여 순열을 만들 수 있다.

단, 이 경우 r의 값이 커지면(골라야 하는 원소가 많아지면) for를 늘리기 어렵다는 문제가 존재한다.

// 3P3
// 0 부터 2사이 하나 선택
for (int i = 0; i < 3; i++) {
    // 0 부터 2 사이 숫자 중,
    for (int j = 0; j < 3; j++) {
        // 앞에서 선택하지 않은 숫자 선택
        if (i == j) continue;

        // 0 부터 2 사이 숫자 중,
        for (int k = 0; k < 3; k++) {
            // 앞에서 선택하지 않은 숫자 선택
            if (i == k || j == k) continue;
            // 출력
            System.out.println(i + " " + j + " " + k);
        }
    }
}

재귀함수로 순열 생성

재귀함수를 이용해 for의 중첩을 해결할 수 있다.

private void permNumbers(
        int n, 
        int r, 
        // 이번 재귀 호출이 몇번째 숫자를 선택하는 것인지
        int k, 
        // 결과 저장용 배열
        int[] perm, 
        // 사용한 요소 확인용 배열
        boolean[] used
) {
    // k == r 이면 순열 완성
    if (k == r) {
        System.out.println(Arrays.toString(perm));
    }
    else {
        for (int i = 0; i < n; i++) {
            // i가 이미 사용되었으면 건너뛴다.
            if (used[i]) continue;
            // 이번에 선택한 결과를 저장한다.
            perm[k] = i;
            // 사용했다고 기록하고,
            used[i] = true;
            // k를 하나 증가해 재귀 호출한다.
            this.permNumbers(n, r, k + 1, perm, used);
            // 재귀 호출이 끝나면 다른 숫자를 고르기 위해 기록을 원복
            used[i] = false;
        }
    }
}

같은 것이 있는 순열 이란?

여러 개의 원소를 나열할 때, 그 원소들 중에 서로 똑같은(구분할 수 없는) 것이