순열, 조합, 팩토리얼 - JavaScript

 

알고리즘 문제를 풀때 재귀적으로 모든 경우의 수에 대해 접근할 때가 있다.

이때 응용할 수 있는 기본적인 팩토리얼, 조합, 순열의 JavaScript 코드를 기록하고 공유한다.

1. 팩토리얼 (Factorial)

[네이버 사전]

1 부터 n 개의 양의 정수를 모두 곱한 것을 n 계승(factorial)이라고 하고, n! 로 나타낸다.
즉, n! = 1 x 2 x 3 x ... x (n-1) x n 이다.

n! = n x (n-1)! 의 성질에서 n이 1일 때, 1 = 1 x 0!이 되므로 0! = 1로 약속한다.

 

JS 구현

재귀함수를 이해하는데 가장 기본적인 예제라고 할 수 있다.

재귀함수와 반복문을 사용한 두 가지 방법으로 구현해 볼 수 있다.

다음에 구현할 순열과 조합에서는 재귀함수를 사용하므로 재귀함수를 더 눈여겨보도록 하자.

 

팩토리얼을 JS로 구현하는 로직은 간단하다.

• 재귀 종료 조건: 1씩 줄어드는 num이 0이 되면 1을 리턴
• 결과값에 다시 팩토리얼의 결과값을 곱해준다. 이때, 팩토리얼에 들어가는 인자에 1을 빼준다.

// 재귀함수
const getFactorial = (num) => {
    if (num < 0) throw new Error('Factorial is only defined for non-negative integer!');
    if (num === 0) return 1;
  return num *= getFactorial(num - 1);
}

const result = getFactorial(3);
console.log(result); // 6

 

2. 조합 (Combination)

[네이버 사전]

서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 택할 때,

이것은 n개에서 r를 택하는 조합이라고 하고,

이 조합의 수를 기호로 nCr와 같이 나타낸다.

 

JS 구현

JavaScript로 조합을 구현하는데 수식은 불필요하지만 어떤 식으로 동작하는지 알아야 한다.

조합 코드가 순열 코드보다 쉽고, 조합 코드에서 한 줄만 변경하면 순열을 구하는 코드를 작성할 수 있다.

조합과 순열의 근본적인 차이는 바로 순서의 여부이다.

4C3의 결과를 배열로 표현하면 아래와 같다.

Input: [1, 2, 3, 4]
Output: [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

 

4C3은 4개 중에 3개를 선택할 때 나올 수 있는 모든 조합을 구한다.

조합의 순서는 상관이 없다.

즉, [1, 2, 3] = [3, 2, 1] 이렇게 순서가 바뀌어도 같은 구성이기 때문에 하나의 조합으로 취급한다.

순열이 조합보다 더 다양한 경우의 수를 포함한다. (nCr x r! = nPr)

 

조합을 JS로 구현하는 로직은 아래와 같다.

• 재귀 종료 조건: 하나를 선택할 때에는 모든 배열의 원소를 리턴
• 순회를 돌 때 모든 원소를 처음부터 끝까지 한번씩 고정 (fixed)
• 고정 (fixed)된 값의 나머지 배열에 대해서 조합을 구하도록 한다. 이때, 선택하는 개수를 하나 줄인다.
• 조합을 만들어온 결과에 fixed 값을 앞에 붙여서 리턴할 배열에 전개 연산자(spread syntax)로 배열화 한 후 리턴한다.
• 2C3, 1C2 같이 n 보다 r이 크면, n 이후로는 getCombinations에 들어갈 reset 배열은 빈 배열이고, arr.forEach()는 undefined 이므로 최종 결과값에 포함되지 않는다.

const getCombinations = (arr, selectNumber) => {
	const result = [];
	if (selectNumber === 1) {
		// 모든 배열의 원소를 1개씩 return
		return arr.map(value => [value]);
	}

	arr.forEach((fixed, index, origin) => {
		const rest = origin.slice(index + 1); // fixed 인덱스 이후 나머지
		const combinations = getCombinations(rest, selectNumber - 1); // 나머지 배열에 대해 조합을 구함
		const attached = combinations.map(combination => [fixed, ...combination]); // 조합에 fixed 붙이기
		result.push(...attached);
	});
	
	return result;
}

const example = [1, 2, 3, 4];
const result = getCombinations(example, 3); // 4C3
console.log(result);
// => [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]

 

3. 순열 (Permutation)

[네이버 사전]

서로 다른 n개의 물건 중에서 r개를 선택하여,

한 줄로 배열하는 것을 n개의 물건에서 r개 택하는 순열이라 하고,

이 순열의 수를 기호 nPr와 같이 나타낸다.

 

JS 구현

조합과 동일하게 수식은 필요없지만 어떤 식으로 동작하는지 알아보자.

순열은 조합에서 확장된 개념이기 때문에 조합을 이해하고 나면 쉬워진다.

조합은 순서에 상관없이 선택한 것이라면, 순열은 순서가 중요하다.

그래서 순열을 구하는 공식은 조합으로부터 도출될 수 있다. (nPr = r! x nCr)

조합에 선택하려는 개수의 factorial을 곱하면 순열을 구하는 공식이 탄생한다.

아래와 같이 [1,2,3,4]에서 3개씩 뽑아 순열을 구한다고 하면, 각각의 조합에서 순서를 바꾸는 경우의 수 3!이 곱해지기 때문에 결합법칙으로 인해서 조합을 구하는 공식에 3!을 곱하는 형태가 된다.

[1, 2, 3] => 이 안에서 순서를 바꾸는 경우의 수 => 3!
[1, 2, 4] => 이 안에서 순서를 바꾸는 경우의 수 => 3!
[1, 3, 4] => 이 안에서 순서를 바꾸는 경우의 수 => 3!
[2, 3, 4] => 이 안에서 순서를 바꾸는 경우의 수 => 3!

 

순열을 JS로 구현하는 로직은 조합과 큰 차이가 없다.

• 순서에 대한 경우의 수를 추가해주면 된다.
• 즉, 조합 코드에서 fixed 하나만 제외한 나머지 요소들을 구하는 코드로 바꾸면 된다.

// 해당하는 fixed를 제외한 나머지 요소
const rest = [...origin.slice(0, index), ...origin.slice(index+1)]

 

순열을 구현한 전체 코드는 아래와 같다.

const getPermutations = (arr, selectNumber) => {
	const result = [];
	if (selectNumber === 1) {
		// 모든 배열의 원소를 1개씩 return
		return arr.map(value => [value]);
	}

	arr.forEach((fixed, index, origin) => {
		const rest = [...origin.slice(0, index), ...origin.slice(index + 1)]; // 해당하는 fixed를 제외한 나머지 요소
		const permutations = getPermutations(rest, selectNumber - 1); // 나머지 배열에 대해 조합을 구함
		const attached = permutations.map(permutation => [fixed, ...permutation]); // 조합에 fixed 붙이기
		result.push(...attached);
	});
	
	return result;
}

const example = [1, 2, 3, 4];
const result = getPermutations(example, 3); // 4C3
console.log(result);
// => [
//   [ 1, 2, 3 ], [ 1, 2, 4 ],
//   [ 1, 3, 2 ], [ 1, 3, 4 ],
//   [ 1, 4, 2 ], [ 1, 4, 3 ],
//   [ 2, 1, 3 ], [ 2, 1, 4 ],
//   [ 2, 3, 1 ], [ 2, 3, 4 ],
//   [ 2, 4, 1 ], [ 2, 4, 3 ],
//   [ 3, 1, 2 ], [ 3, 1, 4 ],
//   [ 3, 2, 1 ], [ 3, 2, 4 ],
//   [ 3, 4, 1 ], [ 3, 4, 2 ],
//   [ 4, 1, 2 ], [ 4, 1, 3 ],
//   [ 4, 2, 1 ], [ 4, 2, 3 ],
//   [ 4, 3, 1 ], [ 4, 3, 2 ]
// ]

 

구현된 코드의 실행 결과가 이해가 안된다면 아래를 펼쳐보자.

arr: [ 1, 2, 3, 4], selectedNumber = 3

fixed: 1, index: 0, origin: [1,2,3,4]

    arr: [2,3,4], selectedNumber: 2

     fixed: 2, index: 0, origin: [2,3,4]

          arr: [3,4], selectedNumber: 1

          return [[3], [4]]

     attached = [ [2, 3], [2, 4] ]

     result = [ [1, 2, 3], [1, 2, 4] ]

     fixed: 3, index: 1, origin: [2,3,4]

          arr: [2,4], selectedNumber: 1

          return [[2], [4]]

     attached = [ [3, 2], [3, 4] ]

     result = [ [1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 4] ]

     fixed: 4, index: 2, origin: [2,3,4]

          arr: [2,3], selectedNumber: 1

          return [[2], [3]]

     attached = [ [4, 2], [4, 3] ]

     result = [ [1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 4], [1, 4, 2], [1, 4, 3] ]

fixed: 2, index: 1, origin: [1,2,3,4]

     arr: [1,3,4], selectedNumber: 2

     fixed: 1, index: 0, origin: [1,3,4]

          arr: [3,4], selectedNumber: 1

          return [[3], [4]]

     attached = [ [1, 3], [1, 4] ]

      result = [

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

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

      ]

     fixed: 3, index: 1, origin: [1,3,4]

          arr: [1,4], selectedNumber: 1

          return [[1], [4]]

     attached = [ [3, 1], [3, 4] ]

      result = [

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

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

      ]

     fixed: 4, index: 2, origin: [1,3,4]

          arr: [1,3], selectedNumber: 1

          return [[1], [3]]

     attached = [ [4, 1], [4, 3] ]

      result = [

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

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

      ]

fixed: 3, index: 2, origin: [1,2,3,4]

     arr: [1,2,4], selectedNumber: 2

     fixed: 1, index: 0, origin: [1,2,4]

          arr: [2,4], selectedNumber: 1

          return [[2], [4]]

     attached = [ [1, 2], [1, 4] ]

      result = [

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

          [3, 1, 3], [3, 1, 4]

      ]

     fixed: 2, index: 1, origin: [1,2,4]

          arr: [1,4], selectedNumber: 1

          return [[1], [4]]

     attached = [ [2, 1], [2, 4] ]

      result = [

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

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

      ]

     fixed: 4, index: 2, origin: [1,2,4]

          arr: [1,2], selectedNumber: 1

          return [[1], [2]]

     attached = [ [4, 1], [4, 2] ]

      result = [

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

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

      ]

fixed: 4, index: 3, origin: [1,2,3,4]

     arr: [1,2,3], selectedNumber: 2

     fixed: 1, index: 0, origin: [1,2,3]

          arr: [2,3], selectedNumber: 1

          return [[2], [3]]

     attached = [ [1, 2], [1, 3] ]

      result = [

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

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

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

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

      ]

     fixed: 2, index: 1, origin: [1,2,3]

          arr: [1,3], selectedNumber: 1

          return [[1], [3]]

     attached = [ [2, 1], [2, 3] ]

      result = [

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

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

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

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

      ]

     fixed: 3, index: 2, origin: [1,2,3]

          arr: [1,2], selectedNumber: 1

          return [[1], [2]]

     attached = [ [3, 1], [3, 2] ]

      result = [

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

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

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

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

      ]

---

 

 

어떤 사람에게는 너무 당연할 수도 있다.

그렇지만 누군가에게는 너무 어려울 수도 있다.

그 누군가에게 도움이 되길 바란다.

 

 

 

Reference

JavaScript로 순열과 조합 알고리즘 구현하기