조합 - Combination

간단 설명

• nCr
• n개의 번호가 쓰인 공 중에서 r개를 순서 없이 뽑을 경우의 수
• 순서가 없다는 점에서 순열과 다르다.

예시

3C2

• 3개의 공들 중 2개를 뽑아 나열할 경우의 수
• ab=ba라서 순열과 다르다.

  

  

  안과 시력검사표처럼 생겼다.

• 코드로 표현하면 아래와 같다.
  in = [a,b,c]
  out = [[a,b],[a,c],[b,c]]

수학식

Js 코드로 구현하면?

• [1,2,3,4] 중에 3개를 조합으로 뽑으려면 (=4C3)

  1. 시작! 1을 고정하고 나머지 2,3,4 중에서 2개씩 조합을 구한다. [2,3],[2,4],[3,4]가 될텐데 이것을 고정된 1 뒤에 붙인다.
     [1,2,3],[1,2,4],[1,3,4]
  2. 2를 고정하고 나머지 3,4 중에서 2개씩 조합을 구한다. [3,4]가 될텐데 이것을 2뒤에 붙인다.
     [2,3,4]
  3. 3을 고정하고 나머지 4 중에서 2개씩 조합을 구한다. 4밖에 없으므로 []이다.
  4. 4를 고정하고 나머지 [] 중에서 2개씩 조합을 구한다. []라서 []이다.
  5. 종료

그냥 외워라.

• 조합 알고리즘은 재귀적인 방식을 사용하여 구현된다. 이를 통해 가능한 모든 조합을 탐색한다.
• 재귀 종료 조건은 선택할 요소의 개수가 1개일 때는 각 요소를 배열로 만들어 반환하고, 재귀 호출이 반복되다가 선택할 요소의 개수가 1이 되면 더 이상 재귀 호출을 하지 않고 결과를 반환한다.

경우의 수 뽑기

// 조합을 구하는 함수
function getCombinations(n, r) {
    const results = [];
    if (r === 1) return n.map(value => [value]); // 각 요소를 배열로 반환

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

    return results;
}

const arr = [3, 2, 5, 1, 4];
const r = 3; // 뽑을 요소의 개수

const combinations = getCombinations(arr, r);

console.log("뽑은 횟수:", combinations.length); // 뽑은 횟수 출력
console.log("뽑은 요소들:", combinations); // 뽑은 요소들 출력

경우의 수 count 구하기

// 팩토리얼을 계산하는 함수
function factorial(n) {
    if (n === 0 || n === 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

// 조합의 경우의 수를 계산하는 함수
function combinationCount(n, r) {
    return factorial(n) / (factorial(r) * factorial(n - r));
}

const arr = [3, 2, 5, 1, 4];
const r = 3; // 뽑을 요소의 개수

const count = combinationCount(arr.length, r);

console.log("조합의 경우의 수:", count);

[출처] 딩코딩 - 알고리즘 뽀개기 - 조합 - 재귀이용

p.s 나 정승제 수학 강의 들었다. 근데 combination이 먼저가 아니라 Permutation를 먼저 학습했어야 했다.