[공식] 순열/조합(javascript)

1. 공부 이유

파이썬으로 공부할 때는 순열과 조합을 풀어내는 알고리즘이 있었으나, 자바스크립트에는 따로 없기 때문에 이번 기회에 공부한다.

2. 조합(Combination)

조합을 구현하는 아이디어는 이것이다.

[1,2,3,4] 중 3개의 원소를 순서없이 고르는 모든 경우의 수를 구한다.

이 때, 1을 선택했을 때 나머지는 [2,3,4]가 남는다.
[2,3,4]에서 2를 선택하면 [3,4]가 남는다.
[3,4]에서 각각 하나씩 뽑게 되면 순서대로 [1,2,3], [1,2,4]가 선택된다.

다음으로 다시 [2,3,4]에서 3을 선택하면 [4]남고
[4]에서 선택할 건 4하나만 있으니 [1,3,4]가 또 선택된다.

다음으로 다시 [2,3,4]에서 4를 선택하면 뒤에 남는 배열이 없기 때문에 끝이 난다.

다시 [1,2,3,4]로 올라가서 이번에는 2를 선택한다.
그러면 나머지는 [3,4]가 남고 여기서는 선택지가 [2,3,4]뿐이다.

이렇게 결과는 [[1,2,3], [1,2,4], [1,3,4], [2,3,4]]이고, 위에 풀이 방식이 재귀형식으로 돌아가는 느낌을 받을 수 있다. 식으로 확인하자.

function getCombinations(arr, num){
  const result = []
  if(num === 1) return arr.map(e=> [e])
  
  arr.forEach((e, i, origin)=>{
  	const rest = origin.slice(i+1)
    const combination = getCombinations(rest, num-1)
    const attached = combination.map(el => [e, ...el])
    result.push(...attached)
  })
  return result
}

2. 순열(permutations)

순열을 구하는 아이디어는 아래이다.

처음에는 어렵게 생각했는데 결국 조합과 다를게 하나도 없다.
조합은 순서를 무시하기 때문에 이미 앞에서 선택한 원소는 다음 선택지에서 빠진다.

하지만 순열은 순서를 중시하기 때문에 앞에서 사용된 원소라도 순서가 다르다면 뒤에서 또 등장할 수 있다. 따라서 위의 조합 공식을 아래의 순열 공식으로 바꾸기 위해서는 딱 한 줄만 바뀌면 된다.

function getPermutations(arr,num){
	const result = []
    if(num === 1) return arr.map(e=> [e])
  
  	arr.forEach((el, index, origin)=> {
    	const rest = [...origin.slice(0,index), ...aroriginr.slice(index+1)]
        const permutation = getPermutations(rest, num-1)
        const attached = permutation.map(el => [e, ...el])
    	result.push(...attached)
    })
  return result
}

3. 참고 자료

자바스크립트로 순열과 조합 알고리즘 구하기