[Javascript]순열과 조합(Permutation & Combination)

순열(javascript)

처음 순열을 배운게 언제였더라. 중학생이었나 초등학생이었나. 고등학생때 까지는 순열과 조합을 자주 헷갈렸고 대학교에 오고 나서는 구분은 잘 하는데 공식을 맨날 까먹는다. 매번 공식을 검색하는것도 지긋지긋. 이번 정리를 계기로 다신 순열조합 문제를 풀 때 검색하는 일이 없었으면 하면서 시작하는 정리글.
(춤추는개발자 님의 JavaScript로 순열과 조합 알고리즘 구현하기 포스팅을 참고했습니다.)

순열(Permutation)

서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수.
(네이버 두산백과)

굳이 예를 들자면 서로 다른 10가지 맛의 마카롱이 눈 앞에 있다. 하지만 마카롱의 칼로리는 어마무시하니까 우리는 이 중 4개만 먹을 것이다. 마카롱을 먹는 순서 또한 중요하다. 딸기맛을 먹고 초코맛을 먹는 것과 초코맛을 먹은 뒤 딸기맛을 먹는 것은 엄연히 다르다. 이 때 마카롱을 먹는 경우의 수를 구하는 것이 순열 문제이다.

nPr=n·(n-1)·(n-2)···(n-r+1)

function permutation(arr, num){
  const res = [];
  if(num === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const rest = [...arr.slice(0,idx), ...arr.slice(idx+1)];
    const permutations = permutation(rest, num-1);
    const attach = permutations.map((permutation) => [v, ...permutation]);
    res.push(...attach);
  })
  return res;
}

조합(Combination)

서로 다른 n개 중에서 r개(n≥r) 취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한 조합이라고 한다. (네이버 두산백과)

조합은 더 간단하다. 위에서는 마카롱을 먹는데 순서를 따지고 있었다. 조합은 그냥 디저트 카페에 가서 10가지 맛의 마카롱 중 맛 별로 하나씩 4가지 맛을 구매하는 경우의 수이다. 순서는 중요치 않다.

function combination(arr, num){
  const res = [];
  if(num === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const rest = arr.slice(idx+1);
    const combinations = combination(rest, num-1);
    const attach = combinations.map((combination) => [v, ...combination]);
    res.push(...attach);
  })
  return res;
}

다른건 다 동일하다. 순열과의 차이점은 순열에서는 원소의 순서도 따져야 했기에 rest로 뽑은 원소를 제외한 모든 원소를 다시 검토해야 했지만 조합은 순서는 상관없이 뽑기만 하면 되기때문에 뽑힌 원소 앞의 원소들은 다시 고려해줄 필요가 없다.