[JS] 19. 나만의 순열/조합 템플릿

11 Jan 2022 in JS

순열, 조합 문제를 여러번 접하며, 템플릿을 만든 후 문제마다 쓰면 편할 것 같다는 생각이 들었다.
이전에는 소수찾기 순열/조합 에 나오는 템플릿을 사용했지만, 알고리즘 스터디를 통해 더 좋은 템플릿을 알게 되었다.
이전보다 훨씬 더 간결한 코드이니 기억해두고 활용하자👍

1. Permutation(순열)

const input = [1, 2, 3];
const result = [];
function permutation(arr, n, bucket) {
  if (n === 0) {
    result.push(bucket);
    return;
  }

  for (let i = 0; i < arr.length; i++) {
    let rest = arr.slice();
    let pick = rest.splice(i, 1);
    permutation(rest, n - 1, bucket.concat(pick));
  }
  return result;

//   [
//   [ 1, 2, 3 ],
//   [ 1, 3, 2 ],
//   [ 2, 1, 3 ],
//   [ 2, 3, 1 ],
//   [ 3, 1, 2 ],
//   [ 3, 2, 1 ]
// ]
}

console.log(permutation(input, 3, []));

2. Combination (조합)

const input = [1, 2, 3, 4];
const result = [];
function combination(arr, n, bucket) {
  if (n === 0) {
    result.push(bucket);
    return;
  }

  for (let i = 0; i < arr.length; i++) {
    let rest = arr.slice(i + 1);
    let pick = arr[i];
    combination(rest, n - 1, bucket.concat(pick));
  }
  return result;
}

console.log(combination(input, 3, []));

// [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]