수학 알고리즘 - 순열과 조합 알고리즘(재귀, 반복문)

순열이란

집합의 요소들을 중복없이 특정한 순서로 나열하는 것을 말합니다.

예를 들어 {1, 2, 3}으로 집합이 주어져있을 때 2개를 순열로 만들면 {1,2},{1,3},{2,1},{2,3},{3,1},{3,2}이 됩니다.

서로 다른 n개의 원소에서 r개를 선택하여 나열하는 경우의 수를 말합니다.

 

조합이란

집합의 요소들 중에서 중복없이 일부를 선택하여 순서에 상관없이 나열하는 것을 말합니다.

예를 들어 {1,2,3}으로 집합이 주어져있을 때 2개를 조합하면 {1,2},{1,3},{2,3}이 됩니다.

서로 다른 n개의 원소에서 r개를 선택하는 경우의 수를 말합니다.

 

반복문을 이용한 조합 코드 예시

function combination(arr) {
 const result = []
 for(let i = 0; i < arr.length; i++) {
  for(let j = i + 1; j < arr.length; j++) {
   result.push([arr[i],arr[j])
  }
 }
 return result
}

반복문을 사용하여 조합을 생성하는 경우, 조합의 길이에 따라 반복문의 중첩 수가 증가하게 됩니다. 

예를 들어, 조합의 길이가 2인 경우에는 두 개의 반복문으로 충분하지만, 조합의 길이가 3이 되면 세 개의 반복문이 필요하고, 조합의 길이가 더 길어질수록 반복문의 중첩 수가 늘어나게 됩니다.

이러한 접근 방식은 코드를 작성하기 어렵고 관리하기 힘들게 만들며, 조합의 길이가 늘어날수록 코드의 확장성이 부족해집니다.

 

재귀를 이용한 조합 코드 예시 1

function combination(arr, r) {
 const result = []
 const n = arr.length
 
 function generate(_arr, start) {
  if(_arr.length === r) {
   result.push([..._arr])
   return
  }
  
  for(let i = start; i < n; i++) {
   _arr.push(arr[i])
   generate(_arr, start+1)
   _arr.pop()
  }
 }
 
 generate([], 0)
 return result
}

조합에 사용할 배열과 조합의 길이를 파라미터로 받습니다.

generate라는 함수가 내부에서 반복문안에 재귀로 돌고 있으면서 조합된 배열과 함께 다음 요소를 선택하기 위한 인덱스를 파라미터로 받습니다.

예를 들어 {1,2,3}에서 조합의 길이가 2인 경우

처음 1이 들어오고 재귀 안에서 반복문을 시작하면서 2가 들어오고 조건문에 의해 리턴되고 pop이 되면서 다시 1만 남습니다 그리고 반복문을 통해 3이 들어오고 조건문에 의해 리턴이 됩니다. 그리고 1이 pop이 됩니다.

다음 요소인 2가 반복해서 결과값에 저장되고 리턴됩니다.

 

재귀를 이용한 조합 코드 예시 2

function combination(arr, r) {
 const result = []
 if(r === 1) return arr.map(e => [e])
 
 arr.forEach((e, idx) => {
  const m = combination(arr.slice(idx+1), r-1)
  const a = m.map(e1 => [e,...e1])
  result.push(...a)
 })
 
 return result
}

배열과 조합의 길이를 받아서 r이 1일때 각각의 단일 배열로 만들어서 리턴합니다.

재귀적으로 돌때 현재 요소를 제외한 나머지 요소와 길이를 1 빼서 조합을 계산합니다.

계산된 결과 값에 현재 요소를 추가한 새로운 조합을 생성한뒤 result에 넣어줍니다.

모든 작업이 완료되면 result를 반환합니다.

 

반복문을 이용한 순열 코드 예시

function permutation(arr) {
 const result = []
 for(let i = 0; i < arr.length; i++) {
  for(let j = 0; j < arr.length; j++) {
   if(i == j) continue
   result.push([arr[i],arr[j])
  }
 }
 return result
}

 순열을 순서가 상관이 있기 때문에 조합에서는 j가 i부터 였지만 j도 i와 마찬가지로 0부터해서 {1,2},{2,1} 나오게끔 반복문을 만들었습니다. 같은 요소는 담을 필요가 없기 때문에 continue로 넘겼습니다.

순열로 만들고 싶은 길이가 길수록 반복문이 필요하기때문에 코드의 확장성이 부족합니다.

 

재귀를 이용한 순열 코드 예시1

function permutation(arr, r) {
 const result = []
 const n = arr.length
 function generate(_arr) {
  if(_arr.length === r) {
   result.push([..._arr])
   return
  }
  
  for(let i = 0; i < n; i++) {
   if(_arr.indexOf(arr[i] === -1) {
    _arr.push(arr[i])
    generate(_arr)
    _arr.pop()
   }
  }  
 }
 generate([], 0)
 return result
}

조합과 코드는 비슷하지만 순열은 순서를 상관하기 때문에 재귀 안에 반복문에서 항상 0을 줘서 배열에 첫번째부분부터 탐색하게끔 했습니다.

하지만 같은 요소가 들어가면 안되기 때문에 조건문을 추가해줬습니다.

 

재귀를 이용한 순열 코드 예시2

function permutation(arr, r) {
 const result = []
 if(r === 1) return arr.map(e => [e])
 
 arr.forEach((e,idx) => {
  const _arr = [...arr.slice(0,idx),...arr.slice(idx+1)]
  const m = permutation(_arr, r - 1)
  const a = m.map(e1 => [e,...e1])
  result.push(...a)
 })
 return result
}

조합의 코드에서 순서를 생각하기 때문에 같은 요소를 제외한 새로운 배열을 재귀로 주고

결과 값을 리턴합니다.

r이 1일때 단일 배열로 리턴하여 원래 있던 요소와 map으로 합칠 수 있습니다.