[알고리즘] 순열, 조합 in JavaScript(Refactoring)

[알고리즘] JS 순열, 조합

 

이전에 작성한 글을 다시 살펴보니 코드가 수정될 필요가 있는 부분이 있어서 새롭게 글을 작성합니다. 기존 글을 고치는 방법도 있지만 기록을 남기는 의미로 새로운 글로 작성합니다.

 

순열

function permutation(array, r, depth = 0, result = []) {
  if(depth == r) {
    // return array.slice(0,r);
    result.push(array.slice(0,r));
    return;
  }
  
  for(let i=depth; i < array.length; i++) {
    [array[i], array[depth]] = [array[depth], array[i]];
    // result.push(permutation(array, r, depth + 1));
    permutation(array, r, depth + 1, result);
    [array[i], array[depth]] = [array[depth], array[i]];
  }
  
  return result;
}

const arr = [1,2,3];
// const result = permutation(arr, 2, 0).reduce((acc, cur) => [...acc, ...cur], []);
const result = permutation(arr, 2, 0);

console.log(result); // [[1,2], [1,3], [2,1], [2,3], [3,2], [3,1]]

result 매개변수를 새로 추가하면서 기존 result에 push 하던 과정이 사라졌습니다. 해당 과정이 사라지게 되면서 배열이 중첩되는 문제가 해결되며 결괏값에서 reduce 연산을 하지 않게 되었습니다. 당시에는 중첩되는 배열만 해결하기 위해서 reduce를 사용했지만, 매개변수를 하나 추가하는 것으로 더 간단하게 해결되었습니다.

 

조합

function combination(n, r, start = 0, result = [], temp = []) {
  if(temp.length == r) {
    // return temp;
    result.push([...temp]);
    return;
  }
  
  // for (let i = start + 1; i < n; i++) {
  for(let i = start; i < n; i++) {
    temp.push(i);
    // result.push([...combination(n, r, i, temp)]);
    combination(n, r, i + 1, result, temp);
    temp.pop();
  }
  
  return result;
}

// const result = combination(3, 2).reduce((acc, cur) => [...acc, ...cur], []);
const result = combination(3, 2);
console.log(result); // [[0, 1], [0, 2], [1, 2]]

순열과 마찬가지로 result 매개변수를 추가하며 reduce 연산을 하지 않도록 변경되었습니다. 또한 기존 함수에서 start가 -1로 시작해 불편함을 느껴서 0으로 계산되도록 수정했습니다.

 

추가적으로 조합의 경우 순서가 상관없기 때문에 결과가 index를 반환합니다. 하지만 문제를 풀다 보면 배열의 값을 가져오는 게 편한 경우가 있기 때문에 이에 해당하는 코드도 작성합니다. temp에 index 대신 원하는 배열의 값을 넣어주면 끝입니다.

function combination(arr, r, start = 0, result = [], temp = []) {
  if(temp.length == r) {
    result.push([...temp]);
    return;
  }
  
  for(let i = start; i < arr.length; i++) {
    temp.push(arr[i]);
    combination(arr, r, i + 1, result, temp);
    temp.pop();
  }
  
  return result;
}

const array = [10,20,30];
const result = combination(array, 2);
console.log(result); // [[10, 20], [10, 30], [20, 30]]

 

두 함수 모두 매개변수로 사용된 result는 함수 외부 변수로 빼내어 사용해도 문제없습니다.

const result = [];

function permutation(arr, r, depth = 0) {
  // 최종 return만 삭제
}

function combination(n, r, start = 0, temp = []) {
  // 최종 return만 삭제
}