재귀를 사용하지 않고 조합(Combination) 구현하기

완전탐색법 알고리즘 문제를 풀던 중에 재귀를 사용하지 않고 조합이나 순열을 어떻게 구현할 수 있을까 하는 호기심이 생겨 구현을 시도해봤다.

n개의 원소 중 순서 상관없이 r개를 선택하는 모든 경우의 수를 반환하는 것이 아니라 모든 경우를 포함한 배열을 반환하는 함수를 구현.

재귀를 사용한 조합(Combination) 구현

function Combination(n, r, arr = []) {
  if (r == 0) return [arr];
  var result = [];
  for (var i = (arr.length ? arr[arr.length - 1] + 1 : 0); i < n; i++) {
    result = result.concat(Combination(n, r - 1, arr.concat(i)));
  }
  return result;
}
// ex) Combination(4,2) = [[0,1], [0,2], [0,3], [1,2], [1,3], [2,4]]

재귀를 사용해서 모든 경우를 포함한 배열을 반환하는 함수를 구현.

var result = [];
function Combination2(n, m, arr = []) {
  if (m == 0) result.push(arr);
  for (var i = (arr.length ? arr[arr.length - 1] + 1 : 0); i < n; i++)
  	Combination2(n, m - 1, arr.concat(i));
}
// ex) Combination(4,2);
// ex) result = = [[0,1], [0,2], [0,3], [1,2], [1,3], [2,4]];

알고리즘 문제같이 잠깐 사용할 때는 전역 변수를 사용해 조금 더 짧게 만들 수 있다.

재귀를 사용하지 않고 구현

function Combination(n, r) {
  if (r == 0) return [];
  var result = [];
  var stack = [0];
  while (stack[0] < n - r + 1) {
    if (stack.length < r) {
      if (n - stack[stack.length - 1] - 1 < r - stack.length) {
        stack.pop();
        stack[stack.length - 1]++;
      } else {
        stack.push(stack[stack.length - 1] + 1);
      }
    } else {
      result.push(stack.slice());
      if (stack[stack.length - 1] == n - 1) stack.pop();
      stack[stack.length - 1]++;
    }
  }
  return result;
}

function Combination(n, r) {
  if (r == 0) return [];
  var result = [];
  var stack = [0];
  while (stack[0] < n - r + 1) {

r이 0인 경우에는 아무것도 선택하지 않는 빈 배열을 반환한다.

스택의 길이가 r이 될 때마다 result에 스택을 push하고 함수가 끝날 때 result를 결괏값으로 반환한다.

스택의 첫 번째 값이 n - r + 1이 되면 남은 값으로는 스택의 길이가 r이 될 때까지 채울 수 없기 때문에 반복문을 종료한다.

while (stack[0] < n - r + 1) {
    if (stack.length < r) {
      if (n - stack[stack.length - 1] - 1 < r - stack.length) {
        stack.pop();
        stack[stack.length - 1]++;
      } else {
        stack.push(stack[stack.length - 1] + 1);
      }
    }

n - stack[stack.length - 1] - 1 값이 r - stack.length 보다 작으면 스택의 길이가 r이 될 때까지 채울 수 없기 때문에 pop을 하고 스택의 top에 있는 값을 1 증가시킨다.

ex) 7 C 4에서 스택이 [0,5, , ]인 상태인 경우 스택의 뒤를 채울 수 없기 때문에 [1, , , ]로 반복문을 다시 시작한다.

그런 경우가 아니라면 스택의 길이가 r이 될 때까지 스택의 top에 있는 값에 1을 더한 값을 스택에 추가한다.

else {
      result.push(stack.slice());
      if (stack[stack.length - 1] == n - 1) stack.pop();
      stack[stack.length - 1]++;
    }

스택의 길이가 r이 되면 result에 stack의 복사본을 추가하고 마지막 값이 n-1이라면 pop하고 마지막에서 두 번째 값을 증가시키고 그렇지 않으면 마지막 값을 1 증가시킨다.

ex) 7 C 3에서 스택이 [0, 1, 2]면 [0, 1, 3]이 되고 [0, 1, 6]이면 [0, 2, ]이 된다.

 

함수 활용

var arr = ['a','b','c','d'];
var combination = Combination(4,2).map(v => v.map(i => arr[i]).join(''));

// combination = ["ab", "ac", "ad", "bc", "bd", "cd"];

이렇게 순서 상관없이 r개 선택한 모든 경우를 쉽게 만들 수 있다.