[Kotlin] Algorithm - Combination

Kotlin

2023-10-06 18:53 (KST)

Language :

Combination

Choose r from different n elements without duplication and list them in order.

Process

Select (fixed) an element from the array.
Find and paste the combination based on the remaining arrangements.
Repeat the above procedure until the number of combined elements (recursive call depth) matches r.

The number of all three combinations in an array [A, B, C, D]

Code 1

private const val alphabets = "ABC"
private val results = mutableListOf<Char>() // Altered Alphabet


fun main() {
    combination(2)
}

/**
 * Combination
 * @param count: Number to be extracted
 * @param index: The index to begin the search. Numbers already extracted do not need to be checked again because they do not take into account the order.
 * @param depth: Number of Extracted
 */
fun combination(count: Int = 0, index: Int = 0, depth: Int = 0) {
    if (depth == count) {
        println("[${results.joinToString(", ")}]") // a complete combination
        return
    }

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

Code 2. Compatible with all data types with generic types

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>>() // the number of all cases

    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
}