[AL] 조합과 순열 - JavaScript

알고리즘 문제를 풀다보면 조합과 순열을 활용해서 푸는 문제가 정말정말정말 많이 나온다. 나도 문제 풀때마다 정리해둔 순열과 조합 코드를 보면서 문제에 맞게 고치는 방식으로 풀고 있는데, 그 코드를 세세하게 정리 해보려고 한다. (조합과 순열의 정의, 이론보단 코드에 집중!)
참고 자료

조합 (Combination)

순서를 따지지 않고 가능한 모든 경우의 수를 만드는 것

순서를 따지지 않는다 ➡ 예를 들어 [1, 3, 4] 와 [4, 1, 3]이라는 두 경우가 있을 때 각 경우의 값은 전부 같지만 순서만 다르게 배열되어 있는 것이므로 같은 경우로 친다는 뜻

구현 코드

const getCombination = (arr, cnt) => {			// 1.
  const results = [];
  if(cnt === 1) return arr.map((v)=>[v]);		// 2.
  
  arr.forEach((fixed, index, origin) => {		// 3.
    const rest = origin.slice(index+1);			// 4. 
    const combinations = getCombination(rest, cnt-1);	// 5.
    const final = combinations.map((c)=>[fixed, ...c]);	// 6.
    results.push(...final);				// 7.
  });
  
  return results;
}

코드 설명

1. 조합을 생성할 배열(arr)과 조합의 길이를 결정하는(cnt)를 매개변수를 받는다.

2. 만약 생성할 조합의 길이가 1 이라면 전달받은 배열을 그대로 return 한다.

3. forEach문을 사용하여 배열의 모든 원소들이 한번씩 고정되게 한다.

   ⚡ forEach문의 각각이 의미하는 것 (출처)
   fixed : 처리할 현재 요소
   index : 처리할 현재 요소의 인덱스
   origin : forEach()를 호출한 배열

4. 고정된 값을 제외한 그 뒤 나머지 값들을 담은 배열

5. 위에서 구한 나머지 배열을 이용하여 길이가 하나 줄어든 조합들을 구한다.

6. 기존에 고정한 값 + 위에서 구한 조합들을 합쳐 최종 조합 배열을 생성한다.

7. 최종 결과를 담는 배열에 push 한다.
   
   

   ---

   
   

순열 (Permutation)

순서를 따지면서 가능한 모든 경우의 수를 만드는 것

순서를 따진다 ➡ 조합과는 반대로 [1, 3, 4] 와 [4, 1, 3]를 다르게 보아 다른 경우로 친다는 뜻

구현 코드

const getPermutations = (arr, cnt) => {					// 1.
  const results = [];
  if(cnt === 1) return arr.map((v)=>[v]);				// 2.
  
  arr.forEach((fixed, index, origin) => {				// 3.
    const rest = [...origin.slice(0,index), ...origin.slice(index+1)];	// 4. 
    const permutations = getPermutations(rest, cnt-1);			// 5.
    const final = permutations.map((p)=>[fixed, ...p]);			// 6.
    results.push(...final);						// 7.
  });
  
  return results;
}

코드 설명

거의 모든 코드가 조합의 코드와 똑같지만 딱 한줄의 코드만 다르게 구현된다.

const rest = [...origin.slice(0,index), ...origin.slice(index+1)];

조합의 경우에는 고정된 값을 제외한 그 뒤 나머지 값들을 담은 배열 을 이용하여 나머지 조합을 구하는 방식으로 구현했었지만 !

순열의 경우에는 순서를 따지기 때문에 고정된 값을 제외한 그 앞의 값들 + 그 뒤 나머지 값들을 담은 배열을 생성하게 된다.