[JavaScript] JavaScript에서 순열과 조합 구현하기

1. 조합 Combination

정의

서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 선택한다고 할 때, 이를 n개에서 r개를 택하는 조합이라고 하고 nCr로 표현할 수 있다.

4C3을 예시로 보자. 4개 중 3개를 선택할 때 나오는 모든 조합을 구한다는 말이다. 이때 조합은 요소의 순서와 상관이 없다.
즉, [1, 2, 3]과 [3, 2, 1]은 하나의 조합으로 취급한다.

arr = [1, 2, 3, 4]
combinationArr = [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

수도코드

위 4C3을 구하는 과정을 예시로 수도코드를 보자.

1을 선택 -> 나머지 [2, 3, 4] 중에서 2개씩 조합 구하기
// [1, 2, 3] [1, 2, 4] [1, 3, 4]

2를 선택 -> 나머지 [3, 4] 중에서 2개씩 조합 구하기
// [2, 3, 4]

3을 선택 -> 나머지 [4] 중에서 2개씩 조합 구하기
// []

4를 선택 -> 나머지 [] 중에서 2개씩 조합 구하기
// []

구현

function getCombinations(arr, r) {
  const results = [];
  if(r === 1) return n.map(v => [v]);
  
  arr.forEach((fixed, idx, origin) => {
    const rest = origin.slice(idx+1);       // 현재 요소를 제외한 나머지 요소
    const combinations = getCombinations(rest, r-1);       // 나머지 요소들 중에서 r - 1 개의 조합 구하기
    const attached = combinations.map(combinations => [fixed, ...combination]);       // 현재 요소와 조합된 나머지 요소들 합치기
    results.push(...attached);
  });
  return results;
}

2. 순열 Permutation

정의

서로 다른 n개의 물건에서 r개를 선택해서 한줄로 배열하는 것을 n개에서 r개를 택하는 순열이라고 하고 nPr로 표현할 수 있다.

4P3을 예시로 보자. 4개 중 3개를 선택할 때 나오는 모든 경우의 수를 구한다는 말이다. 조합은 순서에 상관없이 선택한 것이지만, 순열은 순서가 중요하다. (한 줄로 배열 === 순서 중요)

arr = [1, 2, 3, 4]
permutationArr =  [[ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 2 ], [ 1, 3, 4 ],
  [ 1, 4, 2 ], [ 1, 4, 3 ], [ 2, 1, 3 ], [ 2, 1, 4 ], [ 2, 3, 1 ], [ 2, 3, 4 ],
  [ 2, 4, 1 ], [ 2, 4, 3 ], ... ]

수도코드

위 4P3을 구하는 과정을 예시로 수도코드를 보자.
1, 2, 3, 4를 각각 순서대로 고정하고, 나머지 요소만으로 구성된 배열에서 또 순열을 구한다.(재귀로 구현)

1을 선택 -> 나머지 [2, 3, 4] 중에서 2개 줄세우기 
-> 2 선택 -> 나머지 [3, 4] 중에서 1개 줄세우기 -> 3 / 4 선택

2를 선택 -> 나머지 [1, 3, 4] 중에서 2개 줄세우기
-> 1 선택 -> 나머지 [3, 4] 중에서 1개 줄세우기 -> 3 / 4 선택

3을 선택 -> 나머지 [1, 2, 4] 중에서 2개 줄세우기
-> 1 선택 -> 나머지 [2, 4] 중에서 2개 줄세우기 -> 2 / 4 선택

4를 선택 -> 나머지 [1, 2, 3] 중에서 2개 줄세우기
-> 1 선택 -> 나머지 [2, 3] 중에서 2개 줄세우기 -> 2 / 3 선택

구현

function getPermutations(arr, r) {
  const results = [];
  if(r === 1) return arr.map(v => [v]);
  
  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index+1)];
    const permutations = getPermutations(rest, r-1);
    const attached = permutations.map(v => [fixed, ...v]);
    results.push(...attached);
  });
  return results;
}