[JS] 조합, 순열

❗️ 조합 (이항계수)

• n개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수 (순서X)

  $C(n,k) = \dbinom{n}{k} = \dfrac{P(n,k)}{k!} = \dfrac{n!}{k!\cdot(n-k)!}$

// Example : 4개의 원소에서 3개를 고르는 조합의 경우 
n = 3 , k = 2
Input : [1,2,3]
Output : [[1,2],[1,3],[2,3]]

✅ Backtrack을 이용한 구현

const number = [1,2,3];
const r = 2;

const tmp = [];
function backtrack(cur){
  if (tmp.length === r){
    console.log(tmp);
    return;
  }
  
  for (let i = cur; i < number.length; i++){
  	tmp.push(number[i]);
    backtrack(i+1); // 중복을 허용할 경우 backtrack(i)
    tmp.pop();
  }
}

backtrack(0);

✅ 재귀를 이용한 구현

// 경우의 수를 return
function Fac(n){
  if (n ===0 || n === 1) return 1;
  
  if (n >= 2){
  	return n * Fac(n-1);
  }
}
function Combination(n,k){
  const answer = Fac(n) / (Fac(n-k) * Fac(k));
  return answer;
}

// 경우의 배열을 return
function getCombinations(arr,selectNumber){
  const results = [];
  // n개의 원소에서 1개를 선택하는 경우
  if (selectNumber === 1) return arr.map((el)=>[el]);
  
  // 그 외의 경우
  arr.forEach((fixed,index,origin)=>{
    const rest = origin.slice(index + 1);
    const combinations = getCombinations(rest,selectNumber - 1);
    const attached = combinations.map((el)=>[fixed,...el]);
    results.push(...attached);
  })
  
  return results;
}

❗️ 순열

• 순서 상관 있이 n개의 원소를 가지는 집합에서 k개를 뽑는 경우의 수

  $P(n,k) = n(n-1) \cdot\cdot\cdot (n-k+1)$

✅ Backtrack을 이용한 구현

const number = [1,2,3];
const r = 2;

const tmp = [];
function backtrack(){
  if (tmp.length === r){
    console.log(tmp);
    return;
  }
  
  for (let i = 0; i < number.length; i++){
    if (tmp.includes(number[i])) continue; // 중복을 허용할 경우 삭제
  	tmp.push(number[i]);
    backtrack();
    tmp.pop();
  }
}

backtrack();