[JavaScript] 조합 알고리즘 코드 이해하기

const getCombinations = (arr, selectNumber) => {
  const results = []
  if (selectNumber === 1) return arr.map((value) => [value])
  
  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1)
    const combinations = getCombinations(rest, selectNumber - 1)
    const attached = combinations.map((combination) => [fixed, ...combination])
    results.push(...attached)
  });

  return results
}

const result = getCombinations([1,2,3,4], 3)

console.log(result)
// [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]

 

조합을 사용할 때 검색해 본 결과 위와 같은 코드가 많이 사용되는 것 같아 가져왔다.

재귀함수를 사용하고 있어 처음 봤을 떄 한 번에 이해가 가지 않았다.

해당 함수는 조합을 뽑아낼 배열 arr와 몇 개를 택할지 넘겨주는 selectNumber를 인수로 받고 있다.

 

const getCombinations = (arr, selectNumber) => {
  console.log("함수 시작 arr : ", arr, "selectNumber : ", selectNumber)
  const results = []
  if (selectNumber === 1) {
  	const results =  arr.map((value) => [value])
  	console.log("selectNumber가 1: ", results)
 	return results
  }
  
  arr.forEach((fixed, index, origin) => {
    console.log(`fixed : ${fixed}`)
    const rest = origin.slice(index + 1)
    const combinations = getCombinations(rest, selectNumber - 1)
    const attached = combinations.map((combination) => [fixed, ...combination])
    console.log("attached : ", attached)
    results.push(...attached)
    console.log("현재 results : ", results)
  })

  return results
}

const result = getCombinations([1,2,3,4], 3)

 

어떻게 하면 더욱 쉽게 이해할 수 있을까 고민한 결과 예시를 통해 과정을 보는 것이 좋다고 생각하였다.

콘솔로그를 찍고 결과를 비교적 보기 쉽게 정리하였다.

 

함수 시작 arr: [1, 2, 3, 4], selectNumber: 3
fixed : 1
    함수 시작 arr : [2, 3, 4], selectNumber : 2
    fixed : 2
        함수 시작 arr : [3, 4], selectNumber : 1
        selectNumber가 1 : [[3], [4]]
      attached : [[2, 3], [2, 4]]
      현재 results :  [[2, 3], [2, 4]]
    fixed : 3
        함수 시작 arr : [4], selectNumber : 1
        selectNumber가 1 : [[4]]
      attached : [[3, 4]]
      현재 results : [[2, 3], [2, 4], [3, 4]]
    fixed : 4
        함수 시작 arr : [], selectNumber : 1
        selectNumber가 1 : []
      attached : []
      현재 results : [[2, 3], [2, 4], [3, 4]]
  attached : [[1, 2, 3], [1, 2, 4], [1, 3, 4]]
  현재 results :  [[1, 2, 3], [1, 2, 4], [1, 3, 4]]

fixed : 2
    함수 시작 arr : [3, 4], selectNumber : 2
    fixed : 3
      함수 시작 arr : [4], selectNumber : 1
        selectNumber가 1 : [[4]]
      attached : [[3, 4]]
      현재 results : [[3, 4]]
    fixed : 4
      함수 시작 arr : [], selectNumber : 1
        selectNumber가 1 :  []
      attached :  []
      현재 results : [[3, 4]]
    attached :  [[2, 3, 4]]
    현재 results : [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

fixed : 3
    함수 시작 arr : [4], selectNumber : 2
    fixed : 4
      함수 시작 arr : [], selectNumber : 1
        selectNumber가 1 : []
      attached : []
      현재 results : []
    attached : []
    현재 results : [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
    
fixed : 4
    함수 시작 arr : [], selectNumber : 2
    attached : []
    현재 results : [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

 

요점은 특정 값을 고정(fixed) 후 나머지 값들의 조합을 구하고 마지막에 고정된 값을 포함시키면 된다. [fixed, ...나머지 조합]

고정된 값이 제외하고 조합을 구해야하니 selectNumber를 1씩 줄이고 selectNumber가 1일 때 종료 조건을 설정한다.

 

fixed : 1
    fixed : 2
        selectNumber가 1: [[3], [4]]
      attached : [[2, 3], [2, 4]] // fixed가 2 -> [2, ...[3]], [2, ...[4]]
      현재 results :  [[2, 3], [2, 4]]
    fixed : 3
        selectNumber가 1 : [[4]]
      attached : [[3, 4]] // fixed가 3 -> [3, ...[4]]
      현재 results : [[2, 3], [2, 4], [3, 4]]
    fixed : 4
        selectNumber가 1 : []
      attached : []
      현재 results : [[2, 3], [2, 4], [3, 4]]
  attached : [[1, 2, 3], [1, 2, 4], [1, 3, 4]] // fixed가 1 -> [1, ...[2,3]] ...
  현재 results :  [[1, 2, 3], [1, 2, 4], [1, 3, 4]]

 

해당 값을 '고정한다'라는 표현보다 '무조건 포함한다'라는 표현이 이해하기엔 더 쉽다고 느꼈다.

 

'무조건 1을 포함시킨다'라고 가정하면 구해야할 조합의 수는 2

-> '무조건 2를 포함시킨다'라고 가정하면 남은 자릿수는 1, 남은 자릿수가 1이니 종료 조건 true

-> 2를 무조건 포함시켜야 하니 [2, ...나머지 조합] 리턴

-> 1를 무조건 포함시켜야 하니 [1,...나머지 조합] 리턴

 

 

또한 빈배열인 경우 map을 사용하면 빈배열이 리턴된다.

fixed가 4여도 배열에 아무것도 들어있지 않으니 [].map((value) => [4, ...value])의 결과는 []이다.