[Algorithm] 경우의 수(순열과 조합)

1. 경우의 수

 

경우의 수

어떤 사건 혹은 일이 일어날 수 있는 경우의 가짓수를 수로 표현

• 완전 탐색으로 경우의 수를 푸는 알고리즘
  • 순열(nPr)
  • 조합(nCr)
  • 중복(nH): 서로 다른 n개의 원소 중 r을 중복으로 골라 순서에 상관 있게 나열하는 수

 

1) 순열

: 서로 다른 n개의 원소 중 r을 중복 없이 골라 순서에 상관 있게 나열하는 수

✔ for문

증가 할수록 대처 하는데 한계가 있음

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

function permutation(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i == j) continue; // 중복되면 skip처리
      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);

✔ 재귀함수 🤯

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

function permutation(arr, s, r) {
  // 1. 재귀를 멈출 조건
  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);

2) 조합

: 서로 다른 n개의 원소 중 r을 중복 없이 골라 순서에 상관 없이 나열하는 수

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

✔ 재귀함수 🤯

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 - 1 >= r - s; i++) {
    combination(arr, data, s + 1, i + 1, r);
  }
}
combination(input, output, 0, 0, 2);
console.log(count);