순열(Permutation) 구현

순열이란 무엇인가

순열은 조합과 다른 것이다.

조합은 n개중에서 순서가 고려되지 않는, 즉 앞뒤로 순서를 바꿔도 상관없는 그런걸 뽑는 걸 말한다.

그러나 순열은 n개중에서 순서가 고려되는, 즉 {1, 2}가 {2, 1}와는 다르다고 판단하는 경우의 수를 뽑는 것을 말한다.

여기서 사용되는 변수의 의미는 다음과 같다.

• arr : r 개를 뽑기 위한 베이스가 되는 배열
• output : 뽑힌 'r'개의 값들을 넣은 배열
• visited : 중복해서 뽑지 않기 위해서 체크용도의 배열
• depth : r개만큼 뽑았는지 카운팅하기 위한 변수
• r : 몇개로 이루어진 순열을 만들 것인가? 에 대한 변수

// 순열
// 순서를 지키면서 n 개중에서 r 개를 뽑는 경우
static void permutation(int[] arr, int[] output, boolean[] visited, int depth, int r) {
    if (depth == r) {
        for(int i : output) System.out.print(i + " ");
        System.out.println();
        return;
    }
 
    for (int i=0; i<arr.length; i++) {
        if (!visited[i]) {
            visited[i] = true;
            output[depth] = arr[i];
            permutation(arr, output, visited, depth + 1, r);       
            visited[i] = false;;
        }
    }
}

DFS를 돌면서 모든 인덱스를 방문해서 output에 결과값을 넣고, 이미 들어간 값은 visited를 true값으로 변경해서 중복해서 넣지 않을 수 있도록 한다.

depth값이 r과 같아지면 그때 output에 들어간 값을 출력하면 된다.

그림중에 가장 잘 설명된 그림인 것 같아 가져왔다.

출처 : https://bcp0109.tistory.com/14