[도구, Java] 순열과 조합

 

순열

• 순열: 서로 다른 n개 중에서 r개를 선택해 일렬로 배열하는 경우 

{1, 2, 3, 4}에서 3개를 선택해 일렬로 배열하는 경우에서 1이 맨 앞에 오는 경우를 생각해보자.

 

1 - 2 - 3

1 - 2 - 4

1 - 3 - 2

1 - 3 - 4

1 - 4 - 2

1 - 4 - 3

 

위 순열을 구하기 위한 방법을 구체화해보자.

1. 2번째 칸에 순열에 넣지 않은 숫자를 넣는다. 
2. 넣은 숫자를 방문했다고 체크한다. 
3. 3번째 칸에 순열에 넣지 않은 숫자를 넣는다.
4. 넣은 숫자를 방문했다고 체크한다. 
5. 아직 방문하지 않은 숫자가 있으므로, 다시 2번째 칸으로 돌아가 1번을 반복한다. 

이 패턴을 일반화하면,

1. 선택한 원소를 순열의 index위치에 넣는다. 이때, 해당 원소를 방문한 것으로 체크한다. 
2. 방문하지 않은 원소들 중 하나를 선택한다. 이 원소 역시 방문한 것으로 체크한다. 
3. 1, 2번을 통해 다음 원소는 방문하지 않은 원소들 중 하나이며 이 과정을 재귀적으로 수행한다. 
4. 순열이 완성되면, 한 단계 뒤로 돌아가 다른 원소를 선택한다. (모든 순열을 구하기 위함이다.)

{1, 2, 3, 4, 5}에서 3개의 원소를 선택해 일렬로 나열하는 경우의 수를 구하는 방법을 구현해보자.

public class Main {
    public static void main(String[] args) {
        int[] temp = {1, 2, 3, 4, 5};
        int[] permutation = new int[3];
        boolean[] visited = new boolean[5];

        permute(temp, permutation, visited, 0);
    }

	// temp: 주어진 집합
    // permutation: 현재까지 선택된 순열을 저장할 배열
    // visited: 각 원소의 방문 확인을 위한 배열
    // index: 순열에 원소를 넣을 위치(현재까지 채워진 순열의 길이)
    private static int[] permute(int[] temp, int[] permutation, boolean[] visited, int index) {
        if (index == permutation.length) { // 만들어진 순열 출력
            StringBuilder sb = new StringBuilder();
            for (int num : permutation) {
                sb.append(num + " ");
            }
            System.out.println(sb.toString());
            return permutation;
        }

        for (int i = 0; i < temp.length; i++) {
            if (!visited[i]) { // 아직 방문하지 않은 원소인지 확인
                visited[i] = true; // 해당 원소를 방문했다고 체크
                permutation[index] = temp[i]; // 순열의 index위치에 원소 삽입
                permute(temp, permutation, visited, index + 1); // 다음 index + 1번째로 진행
                visited[i] = false; // 다음 경우의 수를 위해 이전 상태로 되돌림
            }
        }
        return permutation;
    }
}

 

조합

• 조합: 서로 다른 n개 중에서 r개를 선택하는 경우 

{1, 2, 3, 4}에서 3개를 선택하는 경우에서 1을 포함하는 경우를 생각해보자.

 

1 - 2 - 3

1 - 2 - 4

1 - 3 - 4

 

위 조합을 구하기 위한 방법을 구체화해보자.

1. 2번째 칸에 조합에 넣지 않은 숫자를 넣는다. [1, 2]
2. 3번째 칸에 조합에 넣지 않은 숫자를 넣는다. [1, 2, 3]
3. 아직 방문하지 않은 숫자가 있으므로, 다시 2번째 칸으로 돌아가 1번을 반복한다. [1, 2, 4]
4. 2번째 칸에 2를 선택한 상태에서 가능한 모든 조합을 찾았으므로, 2를 제외하고 다음 숫자를 넣는다. [1, 3] 
5. 4번은 크게보면 1번과 똑같으므로 같은 과정을 반복해 조합을 만든다. [1, 3, 4]

이 패턴을 일반화하면,

1. 선택한 원소를 조합의 index위치에 넣는다.
2. 나머지 원소들 중에서 추가로 선택할 원소를 결정하고 이 과정을 재귀적으로 진행한다. 
3. index위치의 원소를 선택하면, index + 1위치의 원소를 선택한다. 이때, 이전 단계들에서 선택된 원소는 제외하고 원소를 선택한다. 
4. 모든 가능한 조합을 찾기 위해, 조합을 완성하면 이전 단계로 돌아가 다른 원소를 선택한다. 

{1, 2, 3, 4, 5}에서 3개의 원소를 선택하는 경우의 수를 구하는 방법을 구현해보자.

public class Main {
    public static void main(String[] args) {
        int[] temp = {1, 2, 3, 4, 5};
        int[] combination = new int[3];

        combine(temp, combination, 0, 0);
    }
	
    
	// temp: 주어진 집합
    // combination: 현재까지 선택된 조합을 저장할 배열
    // index: 현재까지 선택한 조합의 길이(다음에 채울 인덱스)
    // start: 다음 원소를 선택하기 위해 시작할 temp 집합 내의 인덱스
    private static int[] combine(int[] temp, int[] combination, int index, int start) {
        if (index == combination.length) { // 조합을 완성했을 경우, 조합 출력
            StringBuilder sb = new StringBuilder();
            for (int i : combination) {
                sb.append(i + " ");
            }
            System.out.println(sb.toString());
            return combination;
        }

        for (int i = start; i < temp.length; i++) {
            combination[index] = temp[i]; // 현재 원소를 조합에 추가
            combine(temp, combination, index + 1, i + 1); // 현재 선택된 원소를 포함하여, 다음 원소를 선택
        }
        return combination;
    }
}