코틀린 코드로 순열 및 조합을 구하는 코드를 작성해봤습니다.

순열

fun <T> permutation(
    arr: Array<T>,
    n: Int,
    r: Int,
    nowArr: Array<T> = arr.sliceArray(0 until r),
    visited: BooleanArray = BooleanArray(n),
    curSelect: Int = 0
) {
  
    if (r == curSelect) { 
        println(nowArr.contentToString())
        return
    }

    for (i in arr.indices) {
        if (!visited[i]){
            visited[i] = true
            nowArr[curSelect] = arr[i]
            permutation(arr, n, r, nowArr, visited, curSelect + 1)
            visited[i] = false
        }
    }

}

순열(개수)

fun permutationCount(n: Int, r: Int): Int {
    var result = 1
    for (i in 0 until r) result *= (n - i)
    return result
}

조합

	fun <T> combination(
    arr: Array<T>,
    n: Int,
    r: Int,
    nowArr: Array<T> = arr.sliceArray(0 until r),
    curSelect: Int = 0,
    start: Int = 0
) {

    if (r == curSelect) {
        println(nowArr.contentToString())
        return
    }

    for (i in start until arr.size) {
        nowArr[curSelect] = arr[i]
        combination(arr, n, r, nowArr, curSelect + 1, i + 1)
    }

}

조합(개수)

조합은 수식으로 구하는 방법과 dp를 이용한 방법 두가지를 작성했습니다.

val dp = Array<IntArray>(n+1) { IntArray(n+1) { -1 } }

fun combinationCount(n: Int, r: Int): Int {
    if (r == 0 || n == r) return 1
    if (dp[n][r] == -1) dp[n][r] = combinationCount(n - 1, r - 1) + combinationCount(n - 1, r)
    return dp[n][r]
}


fun combinationCount(n: Int, r: Int): Int {
    if (r == 0 || n == r) return 1

    var result = 1
    for (i in 1..r) {
        result *= n - r + i
        result /= i
    }
    return result
}