[자바스크립트] 제너레이터로 순열, 조합 구현하기

1. 조합

재귀함수

제너레이터를 사용하지 않고, 재귀로 조합을 구현할 경우 아래와 같다.

function combination(arr, count){
  if (count === 1) return arr.map((target)=> [target])
  const result = [];
  arr.forEach((num, index)=> {
    const restCombinations = combination(arr.slice(index+1), count-1)
    const tmp = restCombinations.map((target)=> [num, ...target])
    result.push(...tmp);
  })
  return result;
}

 

특정 하나의 값을 고정해두고 나머지 값들을 가지고 조합을 구하고 배열에 추가하는 방식이다.

 

예를 들어 [1,2,3,4]에서 3개의 조합을 구한다고 하면

1을 고정 => 2,3,4 중 2개의 조합을 구함 (재귀함수 동작) => 모든 경우의 수를 result 배열에 추가

2를 고정 => 3,4 중 2개의 조합을 구함 (재귀함수 동작) => 모든 경우의 수를 result 배열에 추가

.

.

.

 

이런식으로 반복한다.

재귀함수는 1개의 조합을 구하는 경우는 각 요소를 담은 배열을 리턴하기만 하면 되므로 [[1], [2], [3], [4]]를 반환한다.

 

제너레이터

제너레이터를 만들려면 제너레이터 함수 `function *`가 필요하다. 

제너레이터를 사용하기 위해서는 forEach와 map을 사용할 수 없기 때문에, 아래와 같이 반복문으로 구현했다.

forEach와 map내부에서 yield를 사용하고 싶다면 제너레이터로 동작할 수 있는 foreach나 map 제너레이터 함수를 따로 정의해서 사용해야한다.

function *combination_2(arr, count){
  for (let index = 0; index < arr.length; index++){
    if (count == 1){
      yield [arr[index]];
    }
    else{
      const restCombinations = combination_2(arr.slice(index+1), count-1);
      for (const value of restCombinations){
        yield [arr[index], ...value]
      }
    }
  }
}

위 코드 동작 방식은 다음과 같다.

for (const value of combination_2(arr, 3)) {
  console.log(value);
}

combination_2(arr, 3)이 호출 되면서 combination_2함수로 제어권이 넘어감

count가 3이기 때문에 아래 코드가 실행되면서 새로운 combination_2()함수 실행. count가 1이 될때까지 반복

const restCombinations = combination_2(arr.slice(index+1), count-1);

 

count가 1이 되면 아래 코드가 실행된다. 이때 yield키워드로 인해, 해당 키워드 라인을 실행하고 함수를 호출한 쪽 (즉 상위 스코프)으로 프로그램 제어권을 넘겨준다.

if (count == 1){
  yield [arr[index]];
}

따라서 상위 함수로 다시 돌아가서 아래 코드가 실행된다.

이때 restCombinations에는 위에서 yield뒤에 있던 [arr[index]]가 반환되어 첫번째 제너레이터로 들어가 있다.

const restCombinations = combination_2(arr.slice(index+1), count-1);
for (const value of restCombinations){
	yield [arr[index], ...value]
}

여기서도 yield로 인해 다시 함수를 호출한 쪽으로 프로그램 제어권이 넘어가게 된다.

 

 

 

즉 아까 그냥 재귀로 구현했을 때와 차이점은, 함수 실행을 전부 끝내는 것이 아니라 함수의 현재 실행 상태를 기억했다가 필요할 때마다 내부적으로 필요한 요소에 접근하는 것이다.

 

함수가 실행될때마다 console.log를 찍어보자

 

왼쪽은 제너레이터로 구현한 조합함수, 오른쪽은 그냥 재귀함수로 구현한 조합 함수를 실행한 것이다.

 

그냥 재귀로 구현한 경우, 호출된 모든 함수가 실행 완료된 이후에 최종적으로 반환된 배열을 반복문을 돌며 출력한다.

제너레이터로 구현한경우 yield로 인해 상위 함수로 프로그램 제어권이 넘어가기 때문에, 함수가 실행되고 value를 반환할 때마다 console.log가 찍히고 다시 함수가 실행된다.

 

 

2. 순열

조합을 구현했다면 순열은 어렵지 않다.

조합과 다르게 순열에서는 순서가 다르면 다른 경우의 수로 고려하기 때문에, 그 부분만 고려해주면 된다.

재귀함수

function permutation(arr, count) {
  if (count === 1) return arr.map((target) => [target]);
  const result = [];
  arr.forEach((num, index) => {
    const restPermutation = permutation(
      [...arr.slice(0, index), ...arr.slice(index + 1)],
      count - 1
    );
    const tmp = restPermutation.map((target) => [num, ...target]);
    result.push(...tmp);
  });
  return result;
}

 

제너레이터

function* permutation_2(arr, count) {
  for (let index = 0; index < arr.length; index++) {
    if (count === 1) {
      yield [arr[index]];
    } else {
      const restPermutation = permutation_2(
        [...arr.slice(0, index), ...arr.slice(index + 1)],
        count - 1
      );
      for (const value of restPermutation) {
        yield [arr[index], ...value];
      }
    }
  }
}