[JS] 순열, 조합 (재귀)

순열과 조합을 코드로 작성하기 위해서는 재귀에 대해서 어느정도 코드를 작성할 줄 알아야 한다. 

내가 생각한 재귀 코드를 작성하는 꿀팁은 아래와 같다. 알고리즘 초보라서 이러한 방식을 차용하고 있는데 다른 꿀팁이 있다면 알려주세요..

1. 가장 쉬운 1항의 값으로 코드를 작성한다.
2. 2항 값으로 코드를 작성하고, 이때 재귀 종료 조건도 같이 생각한다.
3. 완성된 코드로 1항을 다시 테스트한다.
4. 최종적으로 3항을 테스트 하며 코드를 수정한다. 

 

조합

---

조합은 순서를 상관하지 않는다. 즉, [1, 2, 3]과 [3, 2, 1] 은 순서가 바뀌었지만 같은 구성이기 때문에 하나의 조합으로 취급된다. 

function combination(array, cnt) {
  let result = [];

  for (let i = 0; i < array.length; i++) {
    const current = array[i];
    const rest = array.slice(i + 1);

    // 종료 조건
    if (cnt === 1) {
      result.push([current]);
      continue;
    }

    const subResult = combination(rest, cnt - 1);

    subResult.forEach((e) => {
      result.push([current, ...e]);
    });
  }

  return result;
}

위의 코드는 array에 특정 배열이 들어가고, cnt는 해당 배열에서 뽑을 숫자의 개수이다.

예를 들어 array에 [1, 2, 3]이 주어지고, cnt가 2로 주어진다면, [1, 2], [1, 3], [2, 3] 이렇게 3개의 결과값을 추출하면 된다. 

 

1. 먼저 [1, 2, 3]에서 1개의 값만 뽑는다고 가정해보고 코드를 작성한다.

2. 이제 2개의 값을 뽑는다고 가정해보자. 이때 종료조건도 생각해보면서 코드를 작성해야한다.

1을 기준 값으로 정하고 남은 배열인 [2, 3]에서 각각 하나씩 뽑은 후 기준 값 1을 push를 해주면 된다고 생각하면서 코드를 짰다.

 

 

순열

---

순열은 순서가 중요하다. 즉, [1, 2, 3]과 [3, 2, 1]은 다른 구성으로 취급한다. 순열을 구하는 공식은 조합으로부터 도출이 가능하다. 

function permutation(array, cnt) {
  let result = [];

  for (let i = 0; i < array.length; i++) {
    const current = array[i];
    const rest = [...array.slice(0, i), array.slice(i + 1)];

    // 종료 조건
    if (cnt === 1) {
      result.push([current]);
      continue;
    }

    const subResult = permutation(rest, cnt - 1);

    subResult.forEach((e) => {
      result.push([current, ...e]);
    });
  }

  return result;
}

rest으로 선언한 부분만 조합 코드와 다르다.

 

 

---

질문이나 잘못된 점은 댓글로 남겨주세요 :)💖