[Kotlin] 코딩테스트 필수 - 순열, 조합

Python에서는 라이브러리를 통해 간단하기 순열과 조합을 사용할 수 있었다.
Kotlin에는 순열과 조합 라이브러리가 없다.
그렇다면 어떻게 구현할 수 있을까? 템플릿을 만들어보자.

순열

fun <T> permutation(arr: Array<T>, n: Int, r: Int): List<List<T>> {
    val result = mutableListOf<List<T>>()
    val visited = BooleanArray(n)

    fun permute(perm: List<T>) {
        if (perm.size == r) {
            result.add(perm)
            return
        }
        for (i in 0 until n) {
            if (!visited[i]) {
                visited[i] = true
                permute(perm + arr[i])
                visited[i] = false
            }
        }
    }

    permute(emptyList())
    return result
}

조합

fun <T> combination(arr: Array<T>, n: Int, r: Int): List<List<T>> {
    val result = mutableListOf<List<T>>()

    fun combine(start: Int, comb: List<T>) {
        if (comb.size == r) {
            result.add(comb)
            return
        }
        for (i in start until n) {
            combine(i + 1, comb + arr[i])
        }
    }

    combine(0, emptyList())
    return result
}