[알고리즘] Algorithm with Math: 순열 / 조합

순열(Permutation)

    - 요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수

    - nPr = n! / (n-r)!

        5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5x4x3x2x1) / (2x1) = (5x4x3) = 60

    - 요소를 뽑는 개수만큼 반복문 중첩

public static ArrayList<String[]> permutation() {
    String[] cases = new String[]{"도", "개", "걸", "윷", "모"};
    ArrayList<String[]> result = new ArrayList<>();

    for (int i = 0; i < cases.length; i++) {
        for (int j = 0; j < cases.length; j++) {
            for (int k = 0; k < cases.length; k++) {
                if (i == j || j == k || k == i) continue;
                String[] input = new String[]{cases[i], cases[j], cases[k]};
                result.add(input);
            }
      	}
    }
    
    return result;
}

 

조합(Combination)

    - 순서에 상관 없이 요소 n개 중에 m개 뽑는 경우의 수

    - nCr = n! / (r! * (n-r)!)

        순서 상관 없이 5장에서 3장을 선택하는 모든 경우의 수 = 5C3 = (5x4x3x2x1) / (3x2x1) x (2x1)) = (5x4x3) / (3x2x1) = 10

public static ArrayList<String[]> combination() {
    String[] cases = new String[]{"도", "개", "걸", "윷", "모"};
    ArrayList<String[]> result = new ArrayList<>();

    for(int i = 0; i < cases.length; i++) {
        for(int j = i + 1; j < cases.length; j++) {
            for(int k = j + 1; k < cases.length; k++) {
                String[] input = new String[]{cases[i], cases[j], cases[k]};
                result.add(input);
			}
		}
	}

    return result;
}

 

순열과 조합의 한계

    - 개수가 늘어나면 반복문의 수도 늘어나야 해서 비효율적

    - 뽑아야 하는 개수가 변수일 때 대응하기 어려움

        → 재귀를 사용해 해결