[코틀린] 조합, 순열 구현하기

백트래킹을 공부하면서, 백트래킹 대표 입문 문제인 N과 M을 풀어보았다. Python으로 조합과 순열을 사용할 때가 나오면, 이미 구현된 라이브러리를 사용했었다. 그럼 Kotlin에서는 조합, 순열을 사용하려면 어떻게 해야될까 생각을 하였고, 미리 템플릿(?)을 만들어두기로 했다. 

평소에 수학 문제를 풀때 처럼 array와 n, r 값만 입력하면, List 형태로 결과가 나오고 이를 가공해서 편한대로 사용할 수 있다. 

순열 \(_nP_r\)

private fun <T> permutation(array: Array<T>, n: Int, r: Int): List<List<T>> {
    val nArray = array.sliceArray(0 until r) //reified type을 쓰지 않고, Array<T>를 사용하기 위해 작성
    val visited = BooleanArray(n)
    val list = mutableListOf<List<T>>()

    fun recursionPermutation(depth: Int = 0) {
        if (depth == r) {
            list.add(nArray.toList()); return
        }

        array.forEachIndexed { index, t ->
            if(!visited[index]) {
                visited[index] = true
                nArray[depth] = t
                recursionPermutation(depth + 1)
                visited[index] = false
            }
        }
    }

    recursionPermutation()
    return list
}

 

🐯 array를 변경해서 테스트 해보세요!! 코드 편집 가능합니다!

 

조합 \(_nC_r\)

private fun <T> combination(array: Array<T>, n: Int, r: Int): List<List<T>> {
    val list = mutableListOf<List<T>>()

    fun recursionCombination(depth: Int = 0, index: Int = 0, resultArray: Array<T> = array.sliceArray(0 until r)) {
        if (depth == r) {
            list.add(resultArray.toList()); return
        }

        for (arrayIndex in index until n) {
            resultArray[depth] = array[arrayIndex]
            recursionCombination(depth + 1, arrayIndex + 1, resultArray)
        }
    }

    recursionCombination()
    return list
}

fun main() {
    combination(arrayOf(1, 2, 3, 4), 4, 3).forEachIndexed { _, ints -> println(ints.joinToString(" ")) }
    combination(arrayOf('a', 'b', 'c'), 3, 2).forEachIndexed { _, ints -> println(ints.joinToString(" ")) }
}

 

🐯 array를 변경해서 테스트 해보세요!! 코드 편집 가능합니다!