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

경우의 수 구하기(순열,중복순열,조합,중복조합) JS

 

작성했던 순열을 구현한 JS 코드 말고 새로운 방식으로 구현한 순열, 조합 구현 코드를 추가하겠습니다.

 

순열

// nPr

// 순열의 결과를 구하고 싶은 array
// n개 중 선택할 개수 r
// 기저사례를 위한 depth

function permutation(array, r, depth) {
  if(r == depth) {
    // array 전체에서 원하는 결과만큼 slice
    // ex) [1,2,3] 중 2개만 원하는 경우 [1,2,3] -> [1,2], [1,3,2] -> [1,3]
    return array.slice(0,r);
  }
  
  const result = [];
  
  for(let i = depth; i < array.length; i++) {
    [array[i], array[depth]] = [array[depth], array[i]]; // swap
    result.push(permutation(array, r, depth + 1));
    [array[i], array[depth]] = [array[depth], array[i]]; // rollback swap
  }
  
  return result;
}

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

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

 

조합

// nCr

// 구하고자 하는 조합의 크기 n
// 원하는 갯수 r
// 다음 인덱스 start
// 조합의 결과 temp

// 조합의 경우 순서에 상관이 없기 때문에 인덱스를 기준으로 한다.
// 또한 값이 같은 경우 헷갈리지 않기 위해 인덱스를 기준으로 한다.
// ex) [2,2,3]와 같은 형태인 경우 인덱스를 기준으로 하지 않으면 헷갈릴 수 있다.

function combination(n, r, start = -1, temp = []) {
  if (temp.length == r) {
    return temp;
  }

  const result = [];

  for (let i = start + 1; i < n; i++) {
    temp.push(i);
    // 불변성을 유지하기 위해서 ...(전개 연산자) 사용
    // 불변성을 유지하지 않으면, 반환되는 값이 temp이기 때문에
    // push, pop 연산의 영향을 받아 result에 빈 배열만이 저장된다.
    result.push([...combination(n, r, i, temp)]);
    temp.pop(); // rollback
  }

  return result;
}

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