순열과 조합 간단정리

오늘도 알고리즘을 풀다가 순열이 헷갈려서...
배운지 10년이 다되가는데 기억이 잘안난다.

순열(Permutation)

서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수.

조합과의 차이점은 순서가 중요할때 라는 것이다!
내가 T1 경기를보고 젠지 경기를 보는건
젠지 경기를 보고 T1 경기를 보는것과 다르다.

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개 취한 조합이라고 한다.

순열과의 차이점은 순서가 중요하지 않다는 것이다

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