조합, 순열, 중복순열 이해하기

ex) [1,2,3] 중에서 2개 뽑기

 

- 조합 (중복 X, 순서 X)

  : [1,2] , [1,3] , [2,3]

 

- 순열 (중복 X, 순서 O)

  : [1,2] , [1,3] , [2,1] , [2,3] , [3,1] , [3,2]

 

- 중복순열 (중복 O, 순서 O)

  : [1,1] , [1,2] , [1,3] , [2,1] , [2,2] , [2,3] , [3,1] , [3,2] , [3,3]  

public class Main {
	// 방문 체크용 배열
    static boolean[] visited;
    //N개중
    static int N;
    //M개뽑기
    static int M;
    static int[] arr;
    static int n = 0; //arr 인덱스

    public static void dfs(int count, int index) {
        if (count == M) { //M개 다 뽑으면 return
            for(int i = 0; i < M; i++){
                System.out.print(arr[i]+" ");
            }
            System.out.println();
            n--;
            return;
        }

        for(int i=index; i<=N; i++){
            if(visited[i]) continue; //방문체크, 중복순열이면 없어도 된다.
            visited[i] = true; 
            arr[n++] = i;
            dfs(count + 1, i+1); //조합이라면 i+1을, 순열이라면 index를 그대로 넣어준다.
            visited[i] = false;
        }
        n--;
    }
    public static void main(String[] args) {
        N = 3; //1,2,3
        M = 2; //2개
        visited = new boolean[N + 1];
        arr = new int[M];
        dfs(0, 1);
    }
}

 

• visited 방문 처리가 안되어 있다면 값을 넣고 방문 체크를 해준 후에 재귀를 호출한다. 
• 이때 매개변수를 살펴보면 (count + 1, i + 1) 이라고 되어 있다. count의 경우에는 몇개를 뽑았는지 세기 위해서 +1 씩 늘려줘야 한다. 그렇다면 i + 1 은 뭘까
• 이 부분이 중요하다. 해당 코드는 조합(중복 X, 순서 O)을 구현한 것으로 순서를 고려하지 않는다. 즉, 순서가 틀려도 값이 같으면 같다고 취급한다.
• 두 번째 매개변수는 i를 초기화할때 사용된다.
• 즉, 재귀호출을 i + 1 을 하게 되면 들어간 값보다 +1 부터 시작하는 것이다. 그럼 중복될 일이 없다.
• 그렇다면, 순열(중복 O, 순서 O) 는 어떻게 구현할까 ?
• 너무 간단하다. i + 1 대신 가장 최초 함수를 호출할때 주어진 index를 그대로 넣어주면 된다.
• 그럼 visited가 중복을 체크해주면서 넣을 수 있는 값은 처음부터 따지게 되므로 {1,2,3} , {2,1,3} 등이 가능해진다.
• 정리하자면, visited는 중복순열(중복O, 순서X) 빼고 모두 필요하다.
• 그리고 조합이라면 i + 1을, 순열이라면 최초 매개변수를 그대로 넣어주면 된다.