순열과 조합

순열 Permutation

서로 다른 n개에서 r개를 골라 순서를 고려해 나열한 경우의 수

수학에서 순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산을 말한다. n개의 원소의 순서를 뒤섞는 순열의 개수는 n!과 같다. 주로 모든 경우의 수를 계산하는 완전 탐색에서 사용한다.

Java로 구현하기

순열 알고리즘

	import java.util.ArrayList;
	import java.util.List;

	public class Permutation {
        private int[] nums; // 순열의 요소
        private int len; // 순열의 길이
        private List<List<Integer>> result; // 결과를 저장하는 리스트

		// 순열의 요소 배열과 원하는 순열의 길이를 파라미터로 받는다
        public List<List<Integer>> permute(int[] nums, int len) {
            this.nums = nums;
            this.len = len;
            result = new ArrayList<>();
            backtrack(new ArrayList<>());
            return result;
        }

        private void backtrack(List<Integer> current) {
            if (current.size() == len) { // 탈출 조건 : 원하는 길이가 됐을 때
                result.add(new ArrayList<>(current));  // 결과를 저장한다
                System.out.println(current); // 확인을 위한 출력
                return; // 탈출
            }
            for (int i = 0; i < nums.length; i++) {
                if (current.contains(nums[i])) { // 이미 해당 수를 저장한 경우 건너뛴다
                    continue;
                }
                current.add(nums[i]); // 수를 추가한다
                backtrack(current); // 현재 리스트를 갖고 다시 재귀
                current.remove(current.size() - 1); // 이미 사용한 경우의 수 제거
            }
        }
	}

실행 결과

int[] nums = {1, 2, 3, 4}
int len = 2

[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 4]
[4, 1]
[4, 2]
[4, 3]

조합 Combination

서로 다른 n개에서 배열을 고려하지 않고 r개를 뽑는 경우의 수

서로 다른 n개의 원소를 갖는 집합에서 순서에 상관없이 r개를 선택하는 경우의 수를 말한다. 순서에 있어 구분이 없다는 점에서 순열과 다르다.

Java로 구현하기

조합 알고리즘

    import java.util.ArrayList;
    import java.util.List;

    public class Combination {

        public List<List<Integer>> findCombination(int n, int k) {
            List<List<Integer>> result = new ArrayList<>(); // 결과를 저장하는 리스트
            // 결과를 저장하는 리스트, 빈 리스트, n까지의 숫자 중에서, k를 선택하는, 1부터
            backtrack(result, new ArrayList<>(), n, k, 1);
            return result;
        }
			
        private void backtrack(List<List<Integer>> result, List<Integer> temp, int n, int k, int start) {
            if (temp.size() == k) { // k개를 선택하면 탈출
                result.add(new ArrayList<>(temp)); // 결과에 저장
                System.out.println(temp); // 확인을 위한 출력
                return;
            }
            for (int i = start; i <= n; i++) { 
                temp.add(i); // 수를 추가한다
                backtrack(result, temp, n, k, i + 1); // 시작하는 수 + 1
                temp.remove(temp.size() - 1); // 이미 사용한 경우의 수 제거
            }
        }
    }

실행 결과

n = 5
k = 3

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

+ 문자열 조합 구하기

	public List<List<String>> findCombination(String[] arr, int k) {
        List<List<String>> result = new ArrayList<>(); // 모든 조합을 저장하는 리스트
        backtrack(result, new ArrayList<>(), arr, k, 0);
        return result; // 결과를 반환
    }

	// 결과를 저장하는 리스트, 빈 리스트, 문자열 배열, 조합의 크기, 시작 인덱스를 파라미터로 받는다
    private void backtrack(List<List<String>> result, List<String> temp, String[] arr, int k, int start) {
        if (temp.size() == k) { // 원하는 조합의 크기가 되면 저장
            result.add(new ArrayList<>(temp));
            System.out.println(temp); // 확인을 위한 출력
            return;
        }
        for (int i = start; i < arr.length; i++) { // 시작 인덱스를 사용한다
            temp.add(arr[i]);
            backtrack(result, temp, arr, k, i + 1); // 시작 인덱스 + 1
            temp.remove(temp.size() - 1); // 이미 사용한 경우의 수 제거
        }
    }

실행 결과

String[] arr = {"a", "b", "c", "d", "e"}
int k = 3

[a, b, c]
[a, b, d]
[a, b, e]
[a, c, d]
[a, c, e]
[a, d, e]
[b, c, d]
[b, c, e]
[b, d, e]
[c, d, e]