[알고리즘] 순열(permutation)과 조합(Combination) 정리

순열(permutation)

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

 

카드 뽑기

A, B, C, D, E로 이뤄진 5장의 카드

순서를 생각하며 3장을 선택할 때 경우의 수

모든 카드를 1장씩 나열하면서, 나열된 카드가 3장에 도달하면 카드의 나열을 중지한다.

• 첫 번째 나열하는 카드를 선택하는 방법에는 다섯 가지가 있다.
• 첫번째 카드를 나열하고 난 다음, 두 번째 카드를 선택하는 방법에는 네 가지가 있다.
• 두번째 카드를 나열하고 난 다음, 세 번째 카드를 선택하는 방법에는 세 가지가 있다.

따라서 5 X 4 X 3 = 60 가지의 방법이 있다.

이렇게 n개 중에서 일부만을 선택하여 나열하는 것을 순열이라고 한다.

순열은 순서를 지키며 나열해야 한다.

 

5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60

일반식 nPr = n! / (n - r)!

 

코드 예제

// 반복문 코드

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;
}

/*
[
  [ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ], [ 'A', 'B', 'E' ],
  [ 'A', 'C', 'B' ], [ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ],
  [ 'A', 'D', 'B' ], [ 'A', 'D', 'C' ], [ 'A', 'D', 'E' ],
  [ 'A', 'E', 'B' ], [ 'A', 'E', 'C' ], [ 'A', 'E', 'D' ],
  [ 'B', 'A', 'C' ], [ 'B', 'A', 'D' ], [ 'B', 'A', 'E' ],
  [ 'B', 'C', 'A' ], [ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ],
  [ 'B', 'D', 'A' ], [ 'B', 'D', 'C' ], [ 'B', 'D', 'E' ],
  [ 'B', 'E', 'A' ], [ 'B', 'E', 'C' ], [ 'B', 'E', 'D' ],
  [ 'C', 'A', 'B' ], [ 'C', 'A', 'D' ], [ 'C', 'A', 'E' ],
  [ 'C', 'B', 'A' ], [ 'C', 'B', 'D' ], [ 'C', 'B', 'E' ],
  [ 'C', 'D', 'A' ], [ 'C', 'D', 'B' ], [ 'C', 'D', 'E' ],
  [ 'C', 'E', 'A' ], [ 'C', 'E', 'B' ], [ 'C', 'E', 'D' ],
  [ 'D', 'A', 'B' ], [ 'D', 'A', 'C' ], [ 'D', 'A', 'E' ],
  [ 'D', 'B', 'A' ], [ 'D', 'B', 'C' ], [ 'D', 'B', 'E' ],
  [ 'D', 'C', 'A' ], [ 'D', 'C', 'B' ], [ 'D', 'C', 'E' ],
  [ 'D', 'E', 'A' ], [ 'D', 'E', 'B' ], [ 'D', 'E', 'C' ],
  [ 'E', 'A', 'B' ], [ 'E', 'A', 'C' ], [ 'E', 'A', 'D' ],
  [ 'E', 'B', 'A' ], [ 'E', 'B', 'C' ], [ 'E', 'B', 'D' ],
  [ 'E', 'C', 'A' ], [ 'E', 'C', 'B' ], [ 'E', 'C', 'D' ],
  [ 'E', 'D', 'A' ], [ 'E', 'D', 'B' ], [ 'E', 'D', 'C' ]
]
*/

반복문의 개수 = 요소를 뽑는 개수

• 5개의 요소 중 3개를 뽑는 조건 : 하나의 반복문당 5개의 요소를 순회하고 반복문을 3번 중첩하여 3개의 요소를 뽑는다.

중복된 요소는 제거

• 같은 인덱스를 선택하는 것은 중복된 요소를 선택한다는 것과 같다. 하지만 순열은 중복된 요소를 허용하지 않기 때문에 동일한 인덱스인지 검사한다.

 

조합(Combination)

순서에 상관없이 요소 N개 중에 M개를 뽑는 경우의 수

 

카드 뽑기

A, B, C, D, E로 이뤄진 5장의 카드

순서를 생각하지 않고 3장을 선택할 때의 모든 경우의 수

모든 경우의 수를 구할 때는 3장을 하나의 그룹으로 선택해야 한다.

• 순열로 구할 수 있는 경우를 찾는다.
• 순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눈다.

순열에서는 A, B, C,     A, C, B,     B, A, C,     B, C, A,    C, A, B,    C, B, A의 여섯 가지는 모두 다른 경우로 취급하지만, 조합에서는 이 여섯 가지를 하나의 경우로 취급한다.

3장의 카드를 순열 공식에 적용한 결과가 (3 X 2 X 1) / 1 = 6이므로 

따라서 (5 X 4 X 3 X 2 X 1) / ((3 X 2 X 1) X (2 X 1)) = 10

 

5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 = 5C3 = 5! / (3! * 2!) = 10

일반식 nCr = n! / (r! * (n - r)!)

 

코드 예제

// 반복문 코드

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++) {
      for(int k = j + 1; k < lookup.length; k++) {
        String[] input = new String[]{lookup[i], lookup[j], lookup[k]};
				result.add(input);
      }
    }
  }

  return result;
}

/*
[
  [ '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' ]
]
*/

순열과 조합은 반복문으로 만들어낼 수는 있지만 한계가 분명하다.

• 개수가 늘어나면 반복문의 수도 늘어난다.
• 뽑아야 되는 개수가 n개처럼 변수로 들어왔을 때 대응이 어렵다.