[COTE] 자바스크립트 조합/순열 + 중복 조합/순열

Number of Cases / Every Cases

- Number of Cases: 가능한 case의 총 갯수

- Every Cases: 발생할 수 있는 모든 경우

1.조합

1) 조합: n개에서 순서에 상관없이 r개를 뽑는 모든 경우의 수
2) 모든 조합의 경우를 구하는 함수 구현 로직:
(1) 전체 배열과 갯수를 인자로 받는 함수를 구현한다.
(2) 1개를 뽑는 경우는 배열의 각 숫자를 배열로 감싸서 리턴한다.(나머지 경우와 통일성을 위해서)
(3) 전체 배열을 돈다. 한개를 선택하고, 그 뒤 남은 것들에 대해서 선택한 1개를 뺀 조합을 구한다.(재귀)
(4) 재귀적으로 돌고 리턴된 것에 선택한 것을 붙여서 리턴한다.

const getCombination = (arr, r) => {
  const result = [];
  
  if(r===1) 
    return arr.map((item)=return [item]});
 
  arr.forEach((item, idx, origin)=>{
    const rest = origin.slice(idx+1);
    const restCombination= getCombination(rest, r-1);
    const merged = restCombination.map((subResult)=>{
      return [item , ... subResult]});
    result.push(merged);
  });
  return result;  
}

 

2.순열

1) 순열: n개에서 r개를 순서를 고려하여 뽑음. 순서만 다른 것에 대해서도 카운트를 하기 때문에 조합보다 경우의 수가 많음.
2) 순열함수 구현 로직:
  ** 조합에서 rest배열을 뒤에 남은거로 주지 않고, 해당 item을 뺀 걸로 구현하면 된다.**

const getPermutation = (arr, r) => {
  const result = [];
  
  if(r===1) 
    return arr.map((item)=return [item]});
 
  arr.forEach((item, idx, origin)=>{
    const rest = [ ... origin.slice(idx-1), ... origin.slice(idx+1)];
    const restPermutation= getPermutation(rest, r-1);
    const merged = restCombination.map((subResult)=>{
      return [item , ... subResult]});
    result.push(merged);
  });
  return result;  
}

---

 

3.중복조합

4.중복순열

 

---

참조:
1. 조합, 순열 코드: https://velog.io/@devjade/JavaScript%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0