[Algorithm] 기본 수학 이론 - 경우의 수 [순열, 조합]

경우의 수

• 어떤 사건 혹은 일이 일어날 수 있는 경우의 거짓수를 수로 표현
• 일상 생활에서의 경우의 수
  • 주사위 : 던지는 결과, 1 ~ 6 사이의 숫자이므로 경우의 수는 6
  • 윷 : 던지는 겨과, 도, 개, 걸, 윷, 모 이므로 경우의 수는 5
  • 가위바위보 : 게임 결과, 가위, 바위, 보 중에 하나를 낼 수 있으므로 경우의 수는 3
  • 동전 : 던지는 결과, 앞면 혹은 뒷면이므로 경우의 수는 2
• 완전 탐색으로 경우의 수를 푸는 알고리즘
  • 순열 : 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수 (nPr)
  • 조합 : 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수 (nCr)
  • 중복 순열 : 서로 다른 n개의 원소 중에서 r개를 중복 있게 골라 순서에 상관 있게 나열하는 경우의 수 (nH)

 

---

 

순열 (Permutation)

• 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수 (nPr)
• 3개의 알파벳으로 단어를 만드는 경우의 수

ex) 재귀

어떻게 구현할 수 있을까? 아까 ABC를 보자. 위에서 나온 모든 경우의 수에서 A를 빼면 BC, CB가 남는다. 이것은 ABC에서 A를 제외하고 구한 순열에, 넣을 수 있는 모든 곳에 A를 넣은 것이다.

즉, 배열이 주어졌을 때 첫 원소를 제외하고 순열을 만든 후에 첫 원소를 넣을 수 있는 모든 곳에 넣어주면 된다.

function getPermutation(elements) {
    // 기저사례: 원소가 하나만 있으면 자기 자신을 반환한다.
    if(elements.length === 1) return [elements];
    const permutations = [];
    
    // 첫 번째 원소를 제외한 순열을 구한다.
    const smallerPermutations = getPermutation(elements.slice(1));

    // 첫 번째 원소를 넣을 수 있는 모든 곳에 넣어준다.
    const fisrtElement = elements[0];
    smallerPermutations.forEach(permutation => {
        for(let positionIndex = 0; positionIndex <= permutation.length; positionIndex++) {
            const prefix = permutation.slice(0, positionIndex);
            const suffix = permutation.slice(positionIndex);
            permutations.push(prefix.concat([fisrtElement], suffix));
        }
    });

    return permutations;
}

let input = ["a", "b", "c"];
let count = 0;

function permutation(arr, s, r) {
  if (s == r) {
    count++;
    console.log(arr.join(" "));
    return;
  }
  
  for (let i = s; i < arr.length; i++) {
    [arr[s], arr[i]] = [arr[i], arr[s]];
    permutation(arr, s + 1, r);
    [arr[s], arr[i]] = [arr[i], arr[s]];
  }
}

permutation(input, 0, 2);
console.log(count);

ex) for문

let input = ["a", "b", "c"];
let count = 0;

function permutation(arr, s, r) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i == j) continue;
      for (let k = 0; k < arr.length; k++) {
        if (i == k) continue;
        if (j == k) continue;
        
        console.log(arr[i], arr[j], arr[k]);
        count++;
      }
    }
  }
}

permutation(input);
console.log(count);

 

---

 

조합 (Combination)

• 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수 (nCr)
• 4개의 숫자 카드에서 2개를 뽑는 경우의 수

 

ex) 재귀

조합을 구현하는 것은 순열과 크게 다르지 않다.

첫 번째 원소부터 시작해서 원소를 제외해서 만든 조합과 합쳐준다. 그 다음부터는 이전 원소를 제외하고 조합을 만든다. 중복되는 조합이 나오지 않게하기 위해서다.

function getCombination(elements, pick) {
    // 기저사례: 골라야 하는 길이가 1이면 각 원소가 조합이 된다.
    if(pick === 1) return elements.map(elem => [elem]);
    
    const combinations = [];
    // 각 원소에 남은 원소로 만들 수 있는 조합들을 붙인다.
    elements.forEach((element, index) => {
        // 만약 남은 원소의 길이가 골라야 하는 길이보다 짧으면 빈 배열이 반환되기 때문에 조합이 생성되지 않는다.
        const smallerCombinations = getCombination(elements.slice(index + 1), pick - 1);
        smallerCombinations.forEach(combination => {
            combinations.push([element].concat(combination));
        });
    });
    return combinations;
}

let input = [1, 2, 3, 4];
let output = [];
let count = 0;

function combination(arr, data, s, idx, r) {
  if (s == r) {
    count++;
    console.log(data);
    return;
  }
  
  for (let i = idx; arr.length - i >= r - s; i++) {
    data[s] = arr[i];
    combination(arr, data, s + 1, i + 1, r);
  }
}

combination(input, output, 0, 0, 2);
console.log(count);

ex) for문

let input = [1, 2, 3, 4];
let count = 0;

function combination(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      count++;
      console.log(arr[i], arr[j]);
    }
  }
}

combination(input);
console.log(count);