[Kotlin] 알고리즘 - 조합(Combination)

조합(Combination)

서로 다른 n개를 가진 원소에서 r개를 중복없이 골라 순서없이 나열한다.

과정

1. 배열에서 원소 하나를 선택(고정)한다.
2. 나머지 배열을 기준으로 조합을 구하여 붙인다.
3. 조합된 원소 개수(재귀호출 깊이)가 r과 일치할 때까지 위 과정을 반복한다.

배열 [A,B,C,D] 중에서 3개를 조합한 모든 경우의 수

코드 1

private const val alphabets = "ABC"
private val results = mutableListOf<Char>() // 정렬된 알파벳


fun main() {
    combination(2)
}

/**
 * 조합
 * @param count: 추출할 개수
 * @param index: 탐색을 시작할 인덱스. 순서를 고려하지 않으므로 이미 추출된 숫자는 다시 확인할 필요가 없다.
 * @param depth: 추출된 개수
 */
fun combination(count: Int = 0, index: Int = 0, depth: Int = 0) {
    if (depth == count) {
        println("[${results.joinToString(", ")}]") // 완성된 조합
        return
    }

    for (i in index until alphabets.length) {
        results.add(alphabets[i])
        combination(count, i + 1, depth + 1)
        results.removeAt(results.lastIndex)
    }
}

코드 2. 제네릭 타입으로 모든 데이터 타입 대응

fun main() {
    combination(arrayOf("A", "B", "C"), 2).forEach {
        println(it)
    }
}

fun <T> combination(elements: Array<T>, r: Int): List<List<T>> {
    val n = elements.size
    val results = mutableListOf<List<T>>() // 모든 경우의 수

    val result = elements.sliceArray(0 until r)

    fun recursionCombination(depth: Int = 0, index: Int = 0) {
        if (depth == r) {
            results.add(result.toList())
            return
        }

        for (i in index until n) {
            result[depth] = elements[i]
            recursionCombination(depth + 1, i + 1)
        }
    }

    recursionCombination()
    return results
}

결과

[A, B]
[A, C]
[B, C]

Reference

https://velog.io/@chayezo/Algorithm-순열-조합

https://hanyeop.tistory.com/455

https://notepad96.tistory.com/111

https://gyeong-log.tistory.com/51

https://soopeach.tistory.com/157

https://velog.io/@heyday_7/알고리즘-순열과-조합

[Kotlin] 알고리즘 - 순열(Permutation) - Dico

알고리즘 조합, 순열, 중복순혈을 kotlin으로 구현

dico.me

[Kotlin] 알고리즘 - 재귀(Recursive) - Dico

알고리즘 재귀(Recursive)를 코틀린으로 설명

dico.me