조합 알고리즘

조합

서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 택할 때, 이것은 n개에서 r개를 택하는 조합이라 하고, 이 조합의 수를 기호로 nCr와 같이 나타낸다.
바로 예를 살펴보도록 하자. 4Combination3 = 4C3을 코드로 구현한다면 다음과 같은 인풋과 아웃풋을 가지게 된다.

재귀함수를 활용한 코드

  const getCombination = function (arr, pickNum) {
   	let result = [];
   	if (pickNum === 1) {
    	return arr.map((input) => [input]);
    }
    
    arr.forEach((fix, index, origin) => {
    const rest = origin.slice(index + 1);
    const comb = getCombination(rest, pickNum - 1);
    const attached = comb.map((c)=> [fix, ...c]);
    result.push(...attached);
    });
    return result;
   }

응용 문제

  /*
   **정수를 요소로 갖는 배열을 입력받아 3개의 요소를 곱해 나올 수 있는 최대값을 리턴해야 하는 문제**
  */
  // 1. 특정 요소들에서 몇 요소를 순서 상관없이 뽑아내는 것이므로 '조합'을 이용한다.
  // 2. 리턴된 배열의 요소 하나씩 곱함 (reduce 사용)
  // 3. 최종 완성된 배열에서 최대값 구함 (내장 객체(Math) or reduce 사용)
  
  
  // arr: 입력받는 정수 요소 배열
  const findMaxCondition = function (arr) {
  	let pickNum = 3;
    
    // 조합 함수 
   const getCombination = function (arr, pickNum) {
   	let result = [];
   	if (pickNum === 1) {
    	return arr.map((input) => [input]);
    }
    
    arr.forEach((fix, index, origin) => {
    const rest = origin.slice(index + 1);
    const comb = getCombination(rest, pickNum - 1);
    const attached = comb.map((c)=> [fix, ...c]);
    result.push(...attached);
    });
    return result;
   }
   
   const combResult = getCombination(arr, pickNum);
  
    
  console.log('combResult: ', combResult);
  
   for (let i = 0; i < combResult.length; i++) {
   	combResult[i] = combResult[i].reduce((acc, cur) => {
   		return acc * cur;
   	}, 1);
   }
  
   const max = combResult.reduce((acc, cur) => {
   		return Math.max(acc, cur)
   });
   return max;
  }
  
  let inputArr = [3,5,1,6];
  console.log('test: ', findMaxCondition(inputArr));

참고) js 문법
reduce : https://miiingo.tistory.com/365
Math.max : http://daplus.net/javascript-math-max-apply-%EB%8A%94-%EC%96%B4%EB%96%BB%EA%B2%8C-%EC%9E%91%EB%8F%99%ED%95%A9%EB%8B%88%EA%B9%8C/