[ Javascript ] 조합, 중복조합, 순열, 중복순열 (feat. 재귀함수)

 

자바스크립트로 재귀함수를 활용해서 조합, 중복조합, 순열, 중복순열을 구현해보자. 아래는 공통적으로 등장하는 변수에 대한 설명이다.

 

1. list → 선택 배열
const list = ['a', 'b', 'c', 'd', 'e'];

2. result → 결과값이 저장되는 배열

3. items → 선택한 요소를 담는 배열

4. k → 선택하는 개수. n_C_k 에서 k를 의미한다

5. idx → list 인덱스 정보

 

구현하는 로직을 간단하게 얘기하면 list에서 선택한 요소를 items 배열에 담는데, items 배열의 크기가 k 가 되면 result 배열에 push 하는 것이다. 

 

 

조합

직관적으로 생각해보자. a ~ e 까지 담긴 배열에서 서로 다른 세 개의 문자를 선택하려고 한다. 어떻게 할 것인가? 아마 대부분 왼쪽부터 순서대로 고를 것이다. 아래 그림처럼 세 개를 다 고르면 다시 돌아가서 다음 것을 고르는 식으로 말이다.

 

이 로직을 그대로 구현하면 된다. 어떻게 하면 될지 잘 생각해보자.

 

조합의 핵심은 화살표가 한 방향으로만 향한다는 것이다. 이는 이전에 선택한 것은 다시 볼 필요가 없다는 뜻이다. 이를 컴퓨터의 관점에서 해석하면 아래와 같다. 

i를 선택했으면 i+1, i+2, i+3, ... 에만 관심있다

 

따라서 조합에는 인덱스 정보가 필요하다. 현재 인덱스를 기준으로 오른쪽 값에만 관심 있기 때문이다. 아래 해법 코드를 보면 함수 인자에 idx가 있는데 이게 list의 인덱스 정보다. idx의 역할은 화살표가 오른쪽 방향으로만 향하게 하는 것으로 이해해도 된다. 

 

이제 코드 설명을 해보겠다. 먼저, 재귀함수이기 때문에 기저조건이 필요하다. 기저 조건은 선택한 요소의 개수가 k와 같아질 때다. 이는 length 메서드를 사용해서 쉽게 구현할 수 있다. 다음으로 함수 내부의 for문을 살펴보자. for문의 초기값은 idx로 조합 함수의 파라미터값이다. 그런데 재귀호출시 자세히 보면 idx 자리에 i+1을 넣어주는 것을 확인할 수 있다. 즉, 다음에 선택 시작점이 되는 idx는 무조건 현재의 i보다 크다는 뜻이다. 재귀호출시 현재 i번째 값을 items에 넣어주고 있는데 이는 선택하는 행위를 뜻한다. 

 

function combination(items, idx, k, list, result) {
  if(items.length === k) {
    result.push(items);
    return;
  }
  for (let i = idx; i < list.length; i ++) {
    combination([...items, list[i]], i + 1, k, list, result);
  }
}

const list = ['a', 'b', 'c', 'd', 'e'];
let result = [];
combination([], 0, 3, list, result);

 

 

중복조합

중복조합은 조합에서 '중복'만 허용하면 된다. 어떻게 중복을 허용하게 할 수 있을까? 해답은 간단하다. 조합은 i번째를 뽑았을 때 i+1번째부터 관심있다면 중복조합은 i번째부터 관심있다. 같은 것을 뽑을 수 있기 때문이다. 조합과 똑같이 이전에 선택한 것에 관심 없지만 현재 선택한 것은 예외다. 이를 컴퓨터의 관점에서 해석하면 아래와 같다. 

 

i를 선택했으면 i, i+1, i+2, ... 에만 관심있다

 

따라서 조합 코드에서 재귀호출을 할 때 idx만 바꿔주면 된다. i+1에서 i로 바꾸면 끝이다. 

 

function pwc(items, idx, k, list, result) {
  if(items.length === k) {
    result.push(items);
    return;
  }

  for (let i = idx; i < list.length; i ++) {
    pwc([...items, list[i]], i, k, list, result);
  }
}

const list = ['a', 'b', 'c', 'd', 'e'];
let result = [];
pwc([], 0, 3, list, result);

 

 

순열

순열과 조합의 가장 큰 차이점은 무엇일까? 바로 '순서'다. 조합은 abc, bca를 서로 같은 것으로 보지만 순열은 다른 것으로 본다. 아까 조합에서 idx의 역할은 화살표가 오른쪽 방향으로만 향하게 하는 것이라고 말했다. 그런데 순열은 다르다. 순열은 순서가 중요하기 때문에 요소를 선택할 때 화살표가 되돌아갈 수 있다. 아래와 같이 말이다. 

그림과 같이 순열은 화살표가 뒤로 갈 수 있기 때문에 idx 변수가 필요 없다. 따라서 for문도 항상 초기값이 0이다. 그러면 순열은 어떻게 구현해야 할까? 

 

기저조건은 조합~중복순열 모두 동일하므로 패스하겠다. 순열은 재귀호출시 list 배열에서 이미 선택한 요소를 제거해서 넘기는 방법으로 구현할 수 있다. 이미 선택한 요소를 제거하는 부분이 list.filter() 부분이다. 몇 가지 예시를 보면 어렵지 않게 이해할 수 있다. 

 

a 선택       → list = [ b, c, d, e]
a, b 선택    → list = [c, d, e]
a, b, c 선택 → list = [d, e]

b 선택       → list = [a, c, d, e]
b, a 선택    → list = [c, d, e]
b, a, c 선택 → list = [d, e]

c 선택       → list = [a, b, d, e]
c, a 선택    → list = [b, d, e]
c, a, b 선택 → list = [d, e]

 

function permutation(items, k, list, result) {
  if(items.length === k) {
    result.push(items);
    return;
  }
  for (let i = 0; i < list.length; i ++) {
    permutation([...items, list[i]], k, list.filter((v, j) => j !== i), result);
  }
}

const list = ['a', 'b', 'c', 'd', 'e'];
let result = [];
permutation([], 3, list, result);

 

중복순열

조합부터 순열까지 잘 이해했다면 설명할 게 없다. 순열 코드에서 재귀호출시 list를 그대로 넘기면 된다. 

function pwr(items, k, list, result) {
  if(items.length === k) {
    result.push(items);
    return;
  }

  for (let i = 0; i < list.length; i ++) {
    pwr([...items, list[i]], k, list, result);
  }
}

const list = ['a', 'b', 'c', 'd', 'e'];
let result = [];
pwr([], 3, list, result);