순열과 조합 알고리즘

그냥....오랜만에 볼 때마다 까먹어서 정리한번. (멍총이🥴)

순열과 조합의 차이

	비교	1,2,3,4,5에서 3개를 뽑는 경우
순열	순서가 있다	123, 213, 321...(모두 다른 경우임)
조합	순서가 없다 (순열에서 공통요소를 제외한)	123==213 (같은 경우)

자바스크립트로 구현하기

- 순열

function permutation(array, m){
    const answer = []
    const checked = Array.from({length: array.length},()=>0) //*중복된 수를 뽑지 않기 위해 필요한 배열
    const tmp = Array.from({length: m}, ()=>0) //*m개를 뽑은 순열을 담는 배열
    
    const dfs = (l) =>{
    	if(l===m){ 				//*뽑은 수가 m개가 되었을 때
        	answer.push(tmp.slice())
        } else {
            for(let i=0; i<arr.length; i++){
            	if(checked[i]!==1){
                    checked[i]=1
                    tmp[l]=array[i]
                    dfs(l+1)
                    checked[i]=0
                 }
            }
        }
    }
    dfs(0) // *시작, 아직 아무 수도 뽑지 않은 경우에서 시작
    return answer;
    
}

permutation([1,2,3], 3)

//[ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ]

---

- 조합

1. nCr = n-1Cr + n-1Cr-1를 적용해본다.

ex) 3C2구하기, 뽑힌 수의 입장에서 생각하기

3C2 : [1,2,3]에서 2개를 뽑는다.

• 3이 포함된 경우 [3, _] : 2C1 (1,2중에 1개를 뽑음)
• 3이 포함되지 않은 경우 [_ , _] : 2C2 (1,2에 2개를 뽑음) =>1 가지 경우
  2C1: [1,2]에서 1개를 뽑는다.
• 2가 포함된 경우 [2] => 1C0(남은 1에서 0개를 뽑음)=>1가지 경우의 수
• 2가 포함되지 않은 경우 [1]=>1C1(남은 1에서 1개를 뽑음) =>1가지 경우의 수
  =>1+1+1=3가지

function Combination(m ,n){
  const tmp = Array.from({ length: m + 1 }, () => Array.from({ length: m + 1 }, () => 0)); //*이중배열
  function dfs(m, n) {
    if (tmp[m][n] > 0) return tmp[m][n];
    if (m === n || n === 0) {
      tmp[m][n] = 1;
      return tmp[m][n];
    }
    tmp[m][n] = dfs(m - 1, n) + dfs(m - 1, n - 1);
    return tmp[m][n];
  }
  return dfs(m, n);
}

Combination(5,3) //*5C3을 구하는 것 => 10가지

2. 연속된 수에서의 조합, 순서가 상관없기 때문에
   이미 뽑은 i는 제외하고 나머지 수 중에 새로 뽑도록 한다 (=>i=s)

function Combination(n, m){
    const answer=[]
    const tmp = Array.from({length: m},()=>0) //*m개를 뽑는 조합이 담긴 배열
    const dfs=(l,s)=>{
    	if(l===m){
        	answer.push(tmp.slice())
        } else {
        	for (let i=s; i<=n; i++){
            	    tmp[l]=i
                    dfs(l+1, i+1)
            }
        }
    }
    dfs(0,array[0])
}

Combination(3, 2)

//[ 1, 2 ], [ 1, 3 ], [ 2, 3 ]

위와 동일한 방식, 한 수는 고정하고 나머지 중에 새로 뽑음
주어진 항목 내에서 원하는 갯수만큼 조합 구하기

function getCombination(arrays, count){
    const result = []
    if(count===1) return arrays.map(el=>[el])
    arrays.forEach((fixed, index, origin)=>{
        //현재 수가 fixed, 나머지가 rest
        const rest = origin.slice(index+1)
        const combinations = getCombination(rest, menu-1)
        const attached = combinations.map(combi=>[fixed,...combi].join(''))
        result.push(...attached)
    })
    return result;    
}

• 위 조합구하는 방식을 사용해 풀은 알고리즘 문제:

  프로그래머스 :메뉴리뉴얼

  내 풀이

function getCombination(order, menu){
    const result = []
    const target = order.sort()
    if(menu===1) return order.map(el=>[el])
    target.forEach((fixed, index, origin)=>{
        //현재 수가 fixed, 나머지가 rest
        const rest = origin.slice(index+1)
        const combinations = getCombination(rest, menu-1)
        const attached = combinations.map(combi=>[fixed,...combi].join(''))
        result.push(...attached)
    })
    return result;    
}

function solution(orders, course) {
    var answer = [];

    for(let menu of course){
        const set = new Set()
        //orders의 각 order에 대해 menu수만큼 조합을 구한다.
        const combiResult = orders.map(order=>getCombination(order.split(''), menu))

        const setted = combiResult.flat()
        setted.forEach(el=>{
            if(set.hasOwnProperty(el)) set[el]+=1
            else set[el]=1
        })
         const setArr = Object.entries(set)
        setArr.sort((a,b)=>b[1]-a[1])
        const hot = setArr[0]
        const samehot = setArr.filter(el=>el[1]===hot[1])

        samehot.forEach(el=> {
            if(el[1]!==1) answer.push(el[0])
        })

        //2이상인 것을 result에 넣는다.
    }
    return answer.sort();
}