순열과 조합

순열과 조합은 코테에서 지겹도록 봐왔지만, 그떄마다 쉽게 끝낸 적이 없는 것 같다. 이번 기회에 그냥 외워버리자.
순열 (중복허용), 조합 (중복비허용)

function permutations(arr, n) {
  let result = [];

  if (n === 1) {
    return arr.map((item) => [item]);
  } else {
    arr.forEach((fixed, index, arr) => {
      const rest = arr.filter((_, idx) => idx !== index);
      const perms = permutations(rest, n - 1);
      const combine = perms.map((v) => [fixed, ...v]);

      result.push(...combine);
    });
  }

  return result;
}

console.log(permutations([1, 2, 3, 4, 5, 6], 2));

=> 1일 경우에는 [1][2]... 으로 나오게 한다. fixed를 제외하고 n - 1하여 재귀를 돌린다. 나온 결과를 fixed와 조합한 뒤, 배열에 저장한다.

function combinations(arr, n) {
  let result = [];

  if (n === 1) {
    return arr.map((item) => [item]);
  } else {
    arr.forEach((fixed, idx, arr) => {
      // 현재 요소 뒤 부터 적용
      const rest = arr.slice(idx + 1);
      const combis = combinations(rest, n - 1);
      const combine = combis.map((v) => [fixed, ...v]);
      result.push(...combine);
    });
  }

  return result;
}
console.log(combinations([1, 2, 3, 4, 5, 6], 2));

=> 1일 경우에는 [1][2]... 으로 나오게 한다. fixed를 제외하고 n - 1하여 재귀를 돌린다. 나온 결과를 fixed와 조합한 뒤, 배열에 저장한다. 다른 부분이 있다면 rest를 구할 때 여기서는 index가 다른 요소를 빼고 나머지가 아니라 현재 인덱스 뒤에 요소로 겹치지 않게 구성