순열과 조합 알고리즘 (자바스크립트/js/javascript)

알고리즘 문제를 풀던 중에, 조합 아이디어를 이용해서 문제를 해결해야 하는 경우가 많이 보이는 것 같아서

이번 시간에는 순열과 조합을 자바스크립트 코드로 작성하는 것에 대해 알아보고자 합니다.

 

우선 순열과 조합의 정의부터 간단히 알아보겠습니다.

 

• 순열 : n개 중에 r개를 뽑아서 순서대로 나열하는 것
  • 예 ) 10P3 = 10*9*8 = 720
• 조합 : 순서 없이 n개 중에 r개를 뽑는 것
  • 예) 10C3 = 10*9*8 / 3*2*1 = 120
  • nCr = nCn-r이므로 10C3 = 10C7

 

1. 조합(Combination)

const getCombinations = (array, selectNumber) => {
    const results = [];
    if(selectNumber === 1){
        return array.map((element) => [element]);
    }
    array.forEach((fixed, index, origin) => {
        const rest = origin.slice(index+1);
        const combinations = getCombinations(rest, selectNumber - 1);
        const attached = combinations.map((combination) => [fixed, ...combination]);
        results.push(...attached);
    });
    return results;
}
console.log(getCombinations([1,2,3,4], 3));

위의 코드의 실행 방식을 하나하나 작성해보면 다음과 같습니다.

• getcombinations([1,2,3,4], 3)
  • fixed : 1, rest = [2,3,4], combinations = getCombinations([2,3,4] ,2)
    • fixed : 2, rest = [3,4] combinations = getCombinations([3,4], 1)
      • if (selectNumber === 1) return [[3],[4]]
      • combinations = [[3],[4]]
      • attached = [[2,3],[2,4]]
      • 현재 results = [[2,3], [2,4]]
    • fixed : 3, rest = [4], combinations = getCombinations([4], 1)
      • if(selectNumber === 1) return [[4]]
      • combinations= [[4]]
      • attached = [[3,4]]
      • 현재 results = [[2,3], [2,4], [3,4]]
    • fixed : 4, rest = [], combinations = getCombinations([], 1)
      • if(selectNumber === 1) return []
      • combinations = []
      • attached = []
      • 현재 results = [[2,3], [2,4], [3,4]]
    • return results = [[2,3], [2,4], [3,4]]
    • combinations = [[2,3], [2,4], [3,4]]
    • attatched = [[1,2,3],[1,2,4],[1,3,4]]
    • 현재 results = [[1,2,3],[1,2,4],[1,3,4]]
  • fixed : 2, rest = [3,4] combinations = getCombinations([3,4], 2)
    • fixed : 3 , rest = [4], combinations = getCombinations([4], 1)
      • if(selectNumber === 1) return [[4]]
      • combinations = [[4]]
      • attached = [[3,4]]
      • 현재 results = [[3,4]]
    • fixed : 4, rest = [] , combinations = getCombinations([], 1)
      • if(selectNumber === 1) return []
      • combinations = []
      • attached = []
      • 현재 results = [[3,4]]
    • return results = [[3,4]]
    • combinations = [[3,4]]
    • attached = [[2,3,4]]
    • 현재 results = [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
  • fixed : 3, rest = [4], combinations = getCombinations ([4], 2)
    • fixed : 4, rest = [], combinations = getCombinations([], 1)
      • if(selectNumber === 1) return []
      • combinations = []
      • attached = []
      • results에 푸쉬안함
    • return results = []
    • combinations = []
    • attached = []
    • results에 푸쉬 안함
    • 현재 results = [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
  • fixed : 4, rest = [] , combinations = getCombinations([], 2)
    • 배열이 이미 텅비어서 getCombinations 실행 안함
    • 현재 results = [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
  • return results = [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

주어진 수가 1,2,3,4 이고 이 중 3개를 조합으로 뽑는다고 했을 때, 문제 해결 전략은 다음과 같습니다.

1,2,3,4 중에서 3개 조합 구하기 => 숫자 하나를 정한 다음, 나머지 중에서 2개 조합 구함 => 하나를 정하고 나머지 중에서 1개 조합 구함

(이 때 숫자 하나를 정하면, 나머지가 다음 차례에 있는 수 중에서만 구성된다. 2를 정했으면 나머지가 3,4가 되는 것이지 1,3,4가 될 수는 없는 것)

 

정답은 [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]로 총 4가지 경우의 수가 나오지만 맨 처음 숫자 1만 fix 했을 때의 경우의 수만 그림으로 살펴보겠습니다.

편의상 [2,3,4]가 답인 경우는 적지 않았습니다. (매커니즘은 같음)

숫자 하나를 고정시키고 나머지 수 중에서 선택하는 수를 하나씩 줄여가며 선택하는 수가 1이 되면 그 값을 배열 형태로 가지고 돌아와서 fix했던 수와 결합시켜서 해당 단계의 반복문이 끝나면 results 배열을 가지고 돌아와서 결국 최상위의 fix했던 수와 결합되어 최종 results가 리턴됩니다.

 

설명은 복잡하지만 재귀함수가 사용되었으며 재귀함수는 가장 안쪽의 함수가 가장먼저 종료되며 어떤 값을 리턴하여 돌려주며 그것을 감싸고 있는 함수가 차례로 종료되는 흐름이라고 생각하면 될 것 같습니다.

 

2. 순열(permutation)

위의 조합을 살펴보았다면 순열은 rest 배열을 구하는 방식만 다르고 매커니즘은 같습니다.

const getPermutations = (array, selectNumber) => {
  const results = [];
  if (selectNumber === 1) {
    return array.map((element) => [element]);
  }
  array.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
    const permutations = getPermutations(rest, selectNumber - 1);
    const attached = permutations.map((permutation) => [fixed, ...permutation]);

    results.push(...attached);
  });
  return results;
};

console.log(getPermutations([1, 2, 3, 4], 3));