순열과 조합 (with JavaScript)

순열과 조합... 중고등학교 때부터 학부까지 그렇게 많이 그 공식을 써왔는데... 이젠 공식조차 기억이 안난다.

그리고 순열과 조합의 각 케이스를 프로그래밍적으로 구하는 건 더더욱 해본적이 없다.

이번에 정리해두고 헷갈릴 때마다 꺼내 쓰자.

 

개념

순열 (Permutation)

서로 다른 n개 중 r개를 순서에 상관있게 선택하는 경우의 수이다.

{1, 2, 3} 중 2개 원소를 선택한다고 하면, {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}의 6가지 경우가 나온다.

공식으로 경우의 수만 구하자면, 아래와 같다.

배열 (Combination)

서로 다른 n개 중 r개를 순서에 상관 없이 선택하는 경우의 수이다.

{1, 2, 3}중 2개의 원소를 선택한다면, {1, 2}, {1, 3}, {2, 3}으로 3가지 경우가 나온다.

공식은,

 

그래서 구현은?

n개의 배열에서 r개의 원소를 선택하는 과정을 구현하려 한다.

순열

순열을 구현하기 위해 경우의 수를 구하는 과정을 살펴보자

{1, 2, 3}에서 2 개를 선택할 때 먼저 맨 앞에 들어갈 하나의 숫자를 정하고, 나머지에서 다른 숫자를 결정한다.

r이 큰 경우에는 숫자 하나를 고르고 나머지에서 하나를 더 고르고 하는 작업을 r번 반복할 것이다.

따라서 재귀함수를 사용하면 저 반복되는 과정을 표현할 수 있다.

function permutation(arr, n) {
  // 종료 조건.
  if (n === 1) {
    return arr.map((val) => [val]);
  }

  let result = [];
  // fixed: 먼저 하나 고른 수
  arr.forEach((fixed, idx, origin) => {
    // fixed를 제외한 나머지에 대해 n - 1개 고르기
    let rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)];
    let perms = permutation(rest, n - 1);
    // n - 1개 집합에 fixed 추가해 n개짜리 배열 완성
    perms.forEach((perm) => {
      result.push([fixed, ...perm]);
    });
  });
  return result;
}

아래 조건으로 테스트를 해보면,

결과가 잘 나오는 것을 확인할 수 있다.

조합

조합도 순열과 비슷하다.

단 다른 점은, 하나의 숫자를 고르면 나머지 중 하나를 고를 때 앞을 보지 않고 뒤만 본다는 점이다.

앞에서 고르는 경우의 수는 이미 앞에 숫자를 고르는 경우에서 다 처리되었기 때문이다.

function combination(arr, n) {
  if (n === 1) {
    return arr.map((val) => [val]);
  }

  let result = [];
  arr.forEach((fixed, idx, origin) => {
    const rest = origin.slice(idx + 1);
    let combs = combination(rest, n - 1);
    combs.forEach((comb) => {
      result.push([fixed, ...comb]);
    });
  });
  return result;
}

'rest'를 구하는 코드만 빼면 완전히 동일한 구조인 것을 알 수 있다.

 

여기서 잠깐 헷갈렸던 부분은 arr.length > n 인 경우 예외 처리가 어떻게 되느냐였는데,

이 경우에는 return 값이 '[]'가 되므로 윗 레벨의 재귀함수에서 combs가 []가 되는 것이고, 따라서 result.push() 자체가 실행이 안되어 자동으로 예외처리 된다.

(이런걸 볼 때마다 알고리즘이란 참 놀랍다)

 

각설하고 이 역시 테스트 해보면,

마찬가지로 잘 나온다.

 

여담

맨 앞에 공식을 보면 바로 알 수 있지만,

무려 시간 복잡도가 무려 O(n!)과 O(2ⁿ)이다...!

따라서 n이 100개는 거뜬히 넘어가는 알고리즘 문제 풀이에는 사용할 수 없다.

그래서 대부분 순열 조합 문제는 n이 10 이하인 경우가 많다고 하니 나름 꿀팁이라고 볼 수 있겠다.