조합 구하기

이 글을 쓴 이유

이전에 조합에 대한 글을 올린적이 있었다. 

https://codevil.tistory.com/6

순열(permutation)과 조합(combination)

그냥 평소에 천천히 여유로울 때는 천천히 잘사용하지만, 문제는 코테중에 갑자기 나타나면 조금 당황을 하는 경우가 있어서 조금 더 직관적인 조합에 대해 새로 정리하기로 했다.

 

어떤 방식을 사용할까?

보통 수학시간이나 경우의 수를 구할 때는 보통 배열에 있는 값들을 한 개씩 넣어가며 경우의 수를 구한다. 문제는 위의 글에서 정리한 방식은 배열에서 필요한 만큼 제외한다.

예시 코드

const getCombinations = (arr, num) =>{
    console.log(arr)
	const result = [];
    if(num===1) return arr.map(v=>[v]);
    arr.forEach((me, i)=>{
    	const rest = arr.slice(i+1);
        const combination = getCombinations(rest, num-1);
        const attached = combination.map((item)=> [me, ...item])
        result.push(...attached)
    })
    return result
}

const data = [1, 2, 3, 4,5];
const r = 3;
const combinations = getCombinations(data, r);
console.log(combinations);

console

[ 1, 2, 3, 4, 5 ]
[ 2, 3, 4, 5 ]
[ 3, 4, 5 ]
[ 4, 5 ]
[ 5 ]
[]
[ 3, 4, 5 ]
[ 4, 5 ]
[ 5 ]
[]
[ 4, 5 ]
[ 5 ]
[]
[ 5 ]
[]
[]
[
  [ 1, 2, 3 ], [ 1, 2, 4 ],
  [ 1, 2, 5 ], [ 1, 3, 4 ],
  [ 1, 3, 5 ], [ 1, 4, 5 ],
  [ 2, 3, 4 ], [ 2, 3, 5 ],
  [ 2, 4, 5 ], [ 3, 4, 5 ]
]

개인적으로는 index와 배열을 합치는 과정에서 신경쓰는 것이 있어서 급할 때 실수가 나오는 것 같았다.

 

해결책

배열에 있는 항목들을 dfs로 돌려가며 넣으며 갯수를 만족하면 배열을 복사하여 push하는 방식을 사용하였다.

예시 코드

function getCombinations(arr, r) {
    const combination = []
    function comb(subnet, pos){
        console.log(subnet)
        if(subnet.length ===r) return combination.push([...subnet])
        for(let i=pos; i<arr.length;i++){
            subnet.push(arr[i])
            comb(subnet, i+1)
            subnet.pop()
        }
    }
    comb([],0)
    return combination
}

const data = [1, 2, 3, 4,5];
const r = 3;
const combinations = getCombinations(data, r);
console.log(combinations);

console

[]
[ 1 ]
[ 1, 2 ]
[ 1, 2, 3 ]
[ 1, 2, 4 ]
[ 1, 2, 5 ]
[ 1, 3 ]
[ 1, 3, 4 ]
[ 1, 3, 5 ]
[ 1, 4 ]
[ 1, 4, 5 ]
[ 1, 5 ]
[ 2 ]
[ 2, 3 ]
[ 2, 3, 4 ]
[ 2, 3, 5 ]
[ 2, 4 ]
[ 2, 4, 5 ]
[ 2, 5 ]
[ 3 ]
[ 3, 4 ]
[ 3, 4, 5 ]
[ 3, 5 ]
[ 4 ]
[ 4, 5 ]
[ 5 ]
[
  [ 1, 2, 3 ], [ 1, 2, 4 ],
  [ 1, 2, 5 ], [ 1, 3, 4 ],
  [ 1, 3, 5 ], [ 1, 4, 5 ],
  [ 2, 3, 4 ], [ 2, 3, 5 ],
  [ 2, 4, 5 ], [ 3, 4, 5 ]
]