[Java Algorithm] Algorithm with Math (순열 / 조합)

순열(permutation)과 조합(Combination)이란?

• 순열 : 요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수.
• 조합 : 순서에 상관없이 요소 n개 중에 m개를 뽑는 경우의 수.

 

공식

팩토리얼 (!)

 

순열 (nPr) : Permutation

 

조합 (nCr) : Combination

 

예시) 반복문을 이용한 카드 뽑기

A, B, C, D, E로 이뤄진 5장의 카드가 있다. 이 5장의 카드 중 3장을 선택하여 나열하려고 한다.

나열 조건

• 순서를 생각하며 3장을 선택 -> 순열
• 순서를 생각하지 않고 3장을 선택 -> 조합

 

case 1. 순서를 생각하며 3장을 선택

공식 대입

5P3 = 5! / (5-3)!

        = (5(5-1)*(5-2)*(5-3)*(5-4)) / 2*(2-1)

        = 60

 

구현 코드

public static ArrayList<String[]> permutationLoop() {

    String[] lookup = new String[]{"A", "B", "C", "D", "E"};
    ArrayList<String[]> result = new ArrayList<>();
	// 반복문의 개수 = 요소를 뽑는 개수
    for (int i = 0; i < lookup.length; i++) {
      for (int j = 0; j < lookup.length; j++) {
        for (int k = 0; k < lookup.length; k++) {
          if (i == j || j == k || k == i) continue; // 동일한 인덱스라면 무시하고 다음으로 넘어감
            String[] input = new String[]{lookup[i], lookup[j], lookup[k]};
            result.add(input);
        }
      }
    }
  return result;
}

 

case 2. 순서를 생각하지 않고 3장을 선택

공식 대입

5C3 = 5! / (5-3)!3!

        = (5(5-1)*(5-2)*(5-3)*(5-4)) / (2(2-1))(3(3-1)(3-2))

        = 10

public static ArrayList<String[]> combinationLoop() {

  String[] lookup = new String[]{"A", "B", "C", "D", "E"};
  ArrayList<String[]> result = new ArrayList<>();

  for(int i = 0; i < lookup.length; i++) {
    for(int j = i + 1; j < lookup.length; j++) { // i 다음 인덱스부터 순회
      for(int k = j + 1; k < lookup.length; k++) { // j 다음 인덱스부터 순회
        String[] input = new String[]{lookup[i], lookup[j], lookup[k]};
				result.add(input);
      }
    }
  }

  return result;
}

 

반복문으로 순열과 조합을 만들어 낼순 있지만, 요소와 변수가 많아질 수록 까다로워진다. 이 때문에 순열과 조합은 재귀로 풀이하는 경우가 많다.