순열/조합 (Permutation / Combination)

1. Combination (조합)

조합 : 순서 없이 n개 중에 r개를 뽑는 것

• 예) 10C3 = 1098 / 321 = 120
• nCr = nCn-r이므로 10C3 = 10C7

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));

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

 

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

 

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

---

2. Permutation (순열)

• 순열 : n개 중에 r개를 뽑아서 순서대로 나열하는 것
  • 예 ) 10P3 = 1098 = 720

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;
};

순열은 rest 배열을 구하는 방식만 다르고 매커니즘은 같습니다.

 

 

> 순열 관련 문제

> 조합 관련 문제