combination.md

조합 (Combination)

집합에서 서로 다른 n개의 원소 중에서 순서와 상관없이 r개를 선택하는 것.

• 장점 : 모든 경우의 수를 구할 수 있는 완전 탐색.
• 단점 : 경우의 수가 많아질수록 계산 시간이 늘어남.

인덱스를 이용한 조합 👍

경우의 수를 순서대로 뽑아낼 수 있는 장점이있고, 코드를 더 직관적으로 짤 수 있음.

const combination = (arr, r) => {
	const result = [];
	com(result, arr, r, Array(r).fill());
	return result;
};
const com = (target, arr, r, picked, deep = 0, pivot = 0) => {
	if (deep === r) {
		target.push(picked.slice());
		return;
	}
	for (let i = pivot; i < arr.length; i++) {
		picked[deep] = arr[i];
		com(target, arr, r, picked, deep + 1, i + 1);
	}
};
const n = 5;
const r = 3;
const arr = Array.from(Array(n).fill(), (_, i) => i + 1);
combination(arr, r).forEach(item => console.log(item));

/* --------------------------------------------------------
[ 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 ]
*/

조합 계산법을 이용한 방법

const n = 5;
const r = 3;
const arr = Array.from(Array(n).fill(), (_, i) => i + 1);
const picked = Array(r);
function Combination(n, r, c) {
	if (r == 0) {
		console.log(picked.slice());
		return;
	}
	if (n < r) {
		return;
	} else {
		picked[r - 1] = arr[n - 1];
		Combination(n - 1, r - 1, c);
		Combination(n - 1, r, c);
	}
}
Combination(n, r, r);
/* ---------------------------------------------
[ 3, 4, 5 ]
[ 2, 4, 5 ]
[ 1, 4, 5 ]
[ 2, 3, 5 ]
[ 1, 3, 5 ]
[ 1, 2, 5 ]
[ 2, 3, 4 ]
[ 1, 3, 4 ]
[ 1, 2, 4 ]
[ 1, 2, 3 ]
*/

const combination = (nums: number[], target: number, cb?: Function, etc?: { deep:number, index:number, coms:number[] }): void => {
  const { deep = 0, index = 0, coms = Array(target) } = { ...etc }
  if (deep === target) {
      cb && cb( ... coms )
    return
  }

  for(let i = index; i < nums.length; i++) {
    coms[deep] = nums[i]
    combination(nums, target, cb, { deep: deep+1, index: i+1, coms })
  }
}

combination([1,2,3,4,5],3,console.log)
/**
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
 * /