[알고리즘] 코틀린 순열, 중복순열, 조합, 중복조합 재귀로 구현하기

2022.02.14 - [알고리즘, 자료구조/기본] - [알고리즘] 자바 순열, 중복순열, 조합, 중복조합 재귀로 구현하기

[알고리즘] 자바 순열, 중복순열, 조합, 중복조합 재귀로 구현하기

위 글에서는 list를 활용하여 순열, 조합을 구했다.

하지만 결과 배열을 따로 선언해놓고 그 값만 바꿔준다면 더 효율적으로 계산할 수 있다.

 

순열, 조합 등의 정의는 위 글에 있으므로 생략하였다.

var max = 3 // 뽑을 숫자 개수
var list = listOf(1,2,3,4,5) // 뽑을 리스트
lateinit var result: Array<Int> // 뽑은 결과
lateinit var visited: Array<Boolean> // 순열 방문 처리

fun main() {
    result = Array(max) {0}
    visited = Array(list.size) {false}

    permutation(0)
    dupPermutation(0)
    combination(0,0)
    dupCombination(0,0)
}

// 순열
fun permutation(count: Int){
    if(count == max){
        println(result.contentDeepToString())
        return
    }

    for(i in 0 until 5){
        if(!visited[i]){
            result[count] = list[i]
            visited[i] = true
            permutation( count + 1)
            visited[i] = false
        }
    }
}

// 중복 순열
fun dupPermutation(count: Int){
    if(count == max){
        println(result.contentDeepToString())
        return
    }

    for(i in 0 until 5){
        result[count] = list[i]
        dupPermutation( count + 1)
    }
}

// 조합
fun combination(index: Int, count: Int){
    if(count == max){
        println(result.contentDeepToString())
        return
    }

    for(i in index until 5){
        result[count] = list[i]
        combination(i + 1, count + 1)
    }
}

// 중복 조합
fun dupCombination(index: Int, count: Int){
    if(count == max){
        println(result.contentDeepToString())
        return
    }

    for(i in index until 5){
        result[count] = list[i]
        dupCombination(i, count + 1)
    }
}