순열과 조합

순열과 조합은 쉽게 수학 공부를 하다보면 확률과 통계에서 접할 수 있는 개념이다. Permutation과 Combination으로 말이다. 예전에 python을 할 때에는 python package에서 순열과 조합을 제공해줬던 것으로 기억한다. 따라서 별 어려움 없이 이를 활용할 수 있었지만, kotlin에서는 그렇지 않다. 그렇기에 kotlin에서 순열과 조합을 구현하는 방법을 알아보자.

조합

조합은 Combination으로 n개의 item 중 k개를 뽑는 방법을 의미한다. 이를 구현하면 아래와 같다. 아래 코드의 기준은 item이 Int일 때의 예시이다.

fun combination(el:List<Int>, k: Int): List<List<Int>> {
	val result = mutableListOf<List<Int>>()
    comb_helper(result, emptyList(), el, k, 0)
	return result
}

fun comb_helper(
	answer: MutableList<List<Int>,
    temp: List<Int>,
    el: List<Int>,
    r: Int,
    start: Int
) {
	if (r==0) {
    	answer.add(temp)
    } else if (el.size-start == r) {
    	answer.add(temp + el.slice(start until el.size))
    } else {
    	for (i in start until el.size) {
        	val cur = temp + el[i]
            comb_helper(answer, cur, el, r-1, i)
        }
    }
}

여러 방식이 있을 수 있겠지만 나는 이 방식을 사용한다. 우선 재귀적으로 불릴 helper function을 이용한다. helper function는 현재까지 뽑은 temp 에다가 r(추가적으로 더 뽑아야할 원소의 갯수)이 0보다 크다면 남은 원소(el 중 start 이후의 원소)들 중 한개를 뽑는 동작을 시행한다. 모든 가능한 선택지에 대해 시도하기 때문에 빼먹는 경우의 수는 없을 것이다.
이 방식을 통해 combination function 내부의 result에 원소를 추가하고, 마지막에 result를 return 하는 것으로 combination을 성공적으로 구현 할 수 있다.

여기까지의 글을 보고 구현이 이해가 안된다면 helper function을 아래와 같은 생각을 가지고 읽어보자.
1. 조합은 n개 중에 k개를 뽑는 것이다.
2. n개 중에 k개를 뽑는 것은 n개 중 임의의 원소 하나를 선택한후 남은 n-1개 중에서 k-1개를 뽑는 것과 동일하다.

순열

순열은 permutation이라고도 하며 특정 원소들을 순서에 상관있어 배열하는 것을 말한다. 사실 정확히는 n개의 원소중 k개의 원소를 중복없이 순서있게 배열하는 것이다. 다만 여기서 나는 구현의 편의를 위해서 n개 중의 k개의 원소는 이미 뽑았다고 가정하고, 이를 순서있게 배열하는 경우의 수를 구하는 것으로 초점을 좁혔다.

구현은 아래와 같다. combination에 비해 코드는 훨씬 간단하다(물론 실제 permutation이 combination을 포함하고 있기에 결국 combination 코드도 작성해야 하는 상황일 가능성이 크다.)

fun permutation(
	el: List<Int>, 
    fin: List<Int> = emptyList(), 
    candidates: List<Int> = el
): List<List<Int>> {
	if (candidates.isEmpty()) {
    	return listOf(fin)
    } else {
    	candidiates.flatMap { permutation(el, fin + it, candidiates - it)
    }
}

flatMap을 이용한 구현이며, 이는 요소들 중 하나씩 선택하가며 순서대로 배치하는 그런 방식이다.

이 구현은 다른 blog를 서칭하다 나오는 여러 구현 들 중 가장 마음에 들어 직접 구현해보며 공부했었다.

활용

이 순열과 조합은 생각보다 쓰임이 많다. 특히 combination의 경우에는 꽤나 유용하게 코딩테스트 문제에서 활용했었다. 다만 주의사항은 명확하다. 이 combination은 특히 꽤나 무겁다. 그래서 돌리는 것 만으로도 큰 시간 복잡도를 잡아먹게 되어있다. 원소들이 너무 많을 경우에는 조합을 사용하는 것이 올바른 풀이가 아닐 수 있으니 한번 재고해보자